[BOJ 15285 // C++] Connections

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

 

이번에 볼 문제는 백준 15285번 문제인 Connections이다.
문제는 아래 링크를 확인하자.

www.acmicpc.net/problem/15285

15285번: Connections

이 문제에서는 주어진 Strongly Connected Graph(각 노드에서 모든 다른 노드로 가는 경로가 존재하는 방향그래프)에서 에지가 2n개인 Strongly Connected Subgraph를 찾는 문제이다.

(정확히는, 2n개의 에지를 제외한 지울 에지를 전부 출력하는 문제이다.)

 

글쓴이는 다음과 같은 아이디어를 바탕으로 이 문제를 해결하였다.

 

노드 X를 하나 정해, 그 노드에서 정방향 에지로 DFS를 하면서 지나는 간선과, 역방향 에지로 DFS를 하면서 지나는 간선만 남아있는 Subgraph 또한 Strongly Connected Graph가 된다. X에서 임의의 노드로 가는 경로가 항상 존재하고(정방향 에지 DFS), 임의의 노드에서 X로 가는 경로가 항상 존재하기 때문이다(역방향 에지 DFS).

 

위 Subgraph는 에지가 최대 2N-2개이므로, 항상 2N개 이하의 에지로 이루어져있다.

 

따라서, (편의상) 1번 노드에서 정방향 에지를 이용한 DFS에 사용된 에지와 역방향 에지를 이용한 DFS에 사용한에지를 제외한 에지에서 개수만 맞춰 아무 에지나 출력하면 된다.

 

아래는 제출한 소스코드이다.

#include <iostream>
#include <vector>
#include <cstring>
using namespace std;

vector<pair<int,int>> G[50001];
vector<pair<int,int>> invG[50001];
bool visited[100001];

bool dfsvisited[100001];
bool invdfsvisited[100001];

void dfs(int current, int parent) {
    for (auto node : G[current]) {
        if (dfsvisited[node.first]) continue;
        dfsvisited[node.first] = 1;
        visited[node.second] = 1;
        dfs(node.first, current);
    }
}

void invdfs(int current, int parent) {
    for (auto node : invG[current]) {
        if (invdfsvisited[node.first]) continue;
        invdfsvisited[node.first] = 1;
        visited[node.second] = 1;
        invdfs(node.first, current);
    }
}

void solve() {
    int V, E; cin >> V >> E;
    
    for (int i = 1;i <= V;i++) {
        G[i].clear();
        invG[i].clear();
    }

    memset(visited, 0, sizeof(visited));
    memset(dfsvisited, 0, sizeof(dfsvisited));
    memset(invdfsvisited, 0, sizeof(invdfsvisited));

    pair<int, int> edge[100001];

    for (int i = 0;i < E;i++) {
        int x, y; cin >> x >> y;
        edge[i] = { x,y };
        G[x].push_back({ y,i });
        invG[y].push_back({ x,i });
    }

    dfsvisited[1] = invdfsvisited[1] = 1;
    dfs(1, 1);
    invdfs(1, 1);

    int cnt = E - V * 2;
    int idx = -1;
    while (cnt > 0) {
        idx++;
        if (visited[idx]) continue;
        cout << edge[idx].first << ' ' << edge[idx].second << '\n';
        cnt--;
    }
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);

    int T; cin >> T;
    for (;T > 0;T--) {
        solve();
    }
}