강한 방향 지정¶
무방향 그래프의 강한 방향 지정(strong orientation)이란 각 간선에 방향을 부여하여 그래프를 강한 연결 그래프로 만드는 것을 말합니다. 즉, 방향을 부여한 후에는 방향 간선을 따라 임의의 정점에서 임의의 정점으로 이동할 수 있어야 합니다.
풀이¶
물론 모든 그래프에 이렇게 할 수 있는 것은 아닙니다. 그래프의 브리지를 생각해 봅시다. 브리지에도 방향을 부여해야 하며, 그렇게 하면 이 브리지는 한 방향으로만 "건널 수 있게" 됩니다. 이는 브리지의 한쪽 끝에서 다른 쪽 끝으로 갈 수 없다는 뜻이므로, 그래프를 강하게 연결된 그래프로 만들 수 없습니다.
이제 브리지가 없는 연결 그래프에서 DFS를 수행한다고 생각해 봅시다. 당연히 모든 정점을 방문하게 됩니다. 그리고 브리지가 없으므로, DFS 트리 간선 중 어느 것을 제거하더라도 역방향 간선을 하나 이상 포함하는 경로를 이용하여 그 간선의 아래쪽에서 위쪽으로 여전히 갈 수 있습니다. 이로부터 어떤 정점에서든 DFS 트리의 루트로 갈 수 있다는 사실이 따라 나옵니다. 또한 DFS 트리의 루트에서는 원하는 어떤 정점이든 방문할 수 있습니다. 강한 방향 지정을 찾았습니다!
다시 말해, 브리지가 없는 연결 그래프에 강한 방향을 지정하려면 그 그래프에서 DFS를 수행한 뒤, DFS 트리 간선은 DFS 루트에서 멀어지는 방향으로, 나머지 모든 간선은 DFS 트리에서 자손으로부터 조상을 향하는 방향으로 지정하면 됩니다.
브리지가 없는 연결 그래프가 곧 강한 방향 지정이 가능한 그래프와 정확히 일치한다는 결과를 Robbins 정리(Robbins' theorem)라고 합니다.
문제 확장¶
SCC의 개수가 최소가 되도록 그래프의 방향을 지정하는 문제를 생각해 봅시다.
물론 그래프의 각 연결 요소는 따로 고려할 수 있습니다. 이제 브리지가 없는 그래프만 강한 방향 지정이 가능하므로, 모든 브리지를 일시적으로 제거해 봅시다. 그러면 브리지가 없는 연결 요소가 여러 개 남게 되며(정확히 처음에 있던 연결 요소의 수 + 브리지의 수만큼), 각각에 강한 방향을 지정할 수 있다는 것을 이미 알고 있습니다.
간선은 제거할 수 없고 방향만 지정할 수 있었지만, 브리지의 방향은 임의로 지정해도 된다는 것이 밝혀집니다. 물론 방향을 지정하는 가장 쉬운 방법은 원래의 각 연결 요소에 대해 위에서 설명한 알고리즘을 수정 없이 그대로 실행하는 것입니다.
구현¶
여기서 입력은 n — 정점의 수, m — 간선의 수이고, 그 뒤에 간선을 설명하는 m개의 줄이 이어집니다.
출력의 첫 번째 줄은 SCC의 최소 개수이고, 두 번째 줄은 m개의 문자로 이루어진 문자열입니다. 각 문자는 > — 입력의 해당 간선이 (입력에 주어진 대로) 왼쪽 정점에서 오른쪽 정점으로 향하도록 방향이 지정되었음을 나타냄 — 또는 < — 그 반대 — 입니다.
이는 간선의 방향도 함께 지정하도록 수정한 브리지 탐색 알고리즘입니다. 첫 번째 단계에서 간선의 방향을 지정하고 두 번째 단계에서 방향이 지정된 그래프의 SCC 개수를 세는 방식으로 구현해도 됩니다.
vector<vector<pair<int, int>>> adj; // adjacency list - vertex and edge pairs
vector<pair<int, int>> edges;
vector<int> tin, low;
int bridge_cnt;
string orient;
vector<bool> edge_used;
void find_bridges(int v) {
static int time = 0;
low[v] = tin[v] = time++;
for (auto p : adj[v]) {
if (edge_used[p.second]) continue;
edge_used[p.second] = true;
orient[p.second] = v == edges[p.second].first ? '>' : '<';
int nv = p.first;
if (tin[nv] == -1) { // if nv is not visited yet
find_bridges(nv);
low[v] = min(low[v], low[nv]);
if (low[nv] > tin[v]) {
// a bridge between v and nv
bridge_cnt++;
}
} else {
low[v] = min(low[v], tin[nv]);
}
}
}
int main() {
int n, m;
scanf("%d %d", &n, &m);
adj.resize(n);
tin.resize(n, -1);
low.resize(n, -1);
orient.resize(m);
edges.resize(m);
edge_used.resize(m);
for (int i = 0; i < m; i++) {
int a, b;
scanf("%d %d", &a, &b);
a--; b--;
adj[a].push_back({b, i});
adj[b].push_back({a, i});
edges[i] = {a, b};
}
int comp_cnt = 0;
for (int v = 0; v < n; v++) {
if (tin[v] == -1) {
comp_cnt++;
find_bridges(v);
}
}
printf("%d\n%s\n", comp_cnt + bridge_cnt, orient.c_str());
}