D번 문제는 그래프 문제로, 관련 내용을 알고 있었다면 쉽게 접근할 수 있는 문제였지만 그렇지 않았다면 어려울 수도 있는 문제였습니다. 주최측의 통계에 따르면, 총 7팀이 풀었고(F나 H보다 적게 풀렸군요-..-) Correct Submissions / Total Submissions 는 약 26.9% 였다고 합니다.

  이 문제를 요약하면, 주어진 그래프가 'Doubly Linked' 되기 위해 추가해야 하는 최소 개수의 에지 수를 구하는 것이 됩니다. 어떤 그래프가 Doubly Linked 되었다 함은, 그래프를 동강내버리기 위해서는 최소 두 개의 간선을 끊어야 함을 의미합니다. 즉, 하나의 간선을 끊어서는 그래프를 분리할 수 없다는 것이지요. 그래프 이론에서는 이를 이중 연결(Biconnected)이라 합니다. 

  (다음 내용은 건너뛰시고 읽으셔도 됩니다)
  비슷한 것으로 Bi-vertex-connected 와 Bi-Edge-connected 라는 게 있습니다. Bi-vertex-connected 는 그래프에서 최소 2개의 점을 끊어야 그래프를 분리할 수 있는 경우이고, Bi-edge-connected 는 그래프에서 최소 2개의 간선을 끊어야 그래프를 분리할 수 있는 경우입니다.

  문제의 그림에서 (a)는 Bi-Edge-connected Graph 이지만 Bi-Vertex-connected Graph 는 아닙니다. 가운데의 점 하나만을 제거해도 되니까요. 이러한 정점들을 절점(Articulation Points)라고 합니다. 마찬가지로 (b)는 Bi-Edge-Connected Graph 가 아닌데, 그 이유는 가운데의 절선 하나만 제거하면 그래프가 쪼개지기 때문입니다. 이러한 간선들을 절선(Bridges)라고 합니다. 이 문제에서 말하는 Doubly Linked 란 Bi-Edge-connected를 의미하는 것이지만, 이 글에서는 biconnected 라는 것을 bi-edge-connected 에 한정하여 사용하도록 하겠습니다 -0- (원래 아무 말 없이 Biconnected 라는 것은 Bi-Vertex-connected 를 의미합니다.)

  어떠한 그래프가 Biconnected 라면, 이 그래프에는 절점과 절선이 없습니다. 즉 이러한 그래프에는 간선을 추가할 필요가 없으므로, 이 그래프 요소들을 모아 하나의 정점으로 생각해 볼 수 있습니다. 이러한 것을 이중 연결 요소(Biconnected Components) 라고 합니다. 그렇다면, 임의의 그래프는 적당히 몇 개의 Biconnected Components 들로 나눌 수 있고, 이 Components 는 각각 하나의 정점이 되는데, 이 정점들을 갖고 만든 그래프는 항상 트리가 됩니다!

  이 트리에서 어떤 두 점을 새로운 간선을 추가하여 잇게 되면, 그 두 점 사이에 있던 모든 점(요소)들은 Biconnected 가 됩니다. 트리에서 두 점 사이의 경로는 유일한데, 간선을 달게 되면 그 경로에 포함되는 모든 점들이 다 하나의 Biconected Compontents 에 들어가게 됩니다.

  목적은 최소 개수의 간선을 이용하여 모든 그래프가 Biconnected 되게 하는 것이므로, 새로운 그래프에서 단말 노드끼리 이어주는게 최적이 된다는 것을 어렵지 않게 알 수 있습니다. 단말 노드가 2L개 있다면, 최소 L개의 간선을 추가해야 하는데 L개만 추가하면 그래프가 모두 이중 연결되므로 답이 L임을 알 수 있습니다. 만약 2L+1개 있다면, L+1개 추가해야 합니다. 즉, 이 그래프(트리)에서 단말 노드의 수를 L이라 할 때, 답은 int((L+1)/2) 가 됨을 알 수 있습니다. 단 모든 그래프가 하나의 이중 연결 요소가 된다면 답은 0이 되겠지요.

  결국 문제는 이중 연결 요소(절점/절선)를 구하는 알고리즘을 작성하는 것입니다. DFS를 사용하는 방법으로 시간복잡도 O(V+E)에 해결할 수 있습니다. 모든 것을 설명하기에는 너무 길기 때문에(....) 인터넷이나 책을 찾아보시면 될 것 같구요(예를 들면 여기), 간단하게 소개하자면, 다음과 같습니다.
  DFS를 하면 간선이 DFS-tree edge와 back edge 두 가지로 나뉘게 됩니다. 그렇다면

dfsnum[u] : DFS 에서의 u 점의 방문 순서
low[u] = min{ dfsnum[u], dfsnum[v] : (u, v)는 back edge, low[v] : (u, v)는 tree edge}

를 구할 수 있고, 어떤 간선이 절선이기 위해서는 tree edge (u, v)에 대하여 low[v] > dfstime[u] 이어야 합니다. 이렇게 DFS를 하고 나면 이중 연결 요소들을 분리해 낼 수 있고, 따라서 이를 갖고 새로운 그래프를 만들어 내시면 됩니다.

Source Code
n이 작기 때문에 인접행렬을 통해 O(n^2) 에 구현한 코드입니다. (인접리스트 등을 사용하면 O(N+M) 에 가능)

#include <stdio.h> #include <memory.h> #pragma warning(disable:4996) #define maxn 1001 int n, m; bool w[maxn][maxn]; // 원래 그래프에서의 인접행렬 bool isbridge[maxn][maxn]; // (u, v)가 절선이면 isbridge[u][v] = 1 bool newgraph[maxn][maxn]; // 이중연결 요소들로 만든 그래프 (인접행렬) int newdegree[maxn]; // 그 그래프에서의 Degree int time = 0, bcc = 0; int low[maxn], dfstime[maxn]; // DFS 용 :) int bccgroup[maxn]; // i번 점이 bccgroup[i]번 요소에 포함됨. int que[maxn], qb, qf; // BFS 용 :) void dfs(int u, int par = -1) { int v; low[u] = dfstime[u] = ++time; for(v=1; v<=n; ++v) if(w[u][v] && v != par) { if(!dfstime[v]) { dfs(v, u); if(low[u] > low[v]) low[u] = low[v]; // (u, v) 가 절선이 됩니다. if(low[v] > dfstime[u]) isbridge[u][v] = isbridge[v][u] = 1; } else if(low[u] > dfstime[v]) low[u] = dfstime[v]; } } int main() { int t; scanf("%d", &t); while(t-- > 0) { scanf("%d %d", &n, &m); // 모든 배열을 초기화 합니다. memset(w, 0, sizeof(w)); memset(isbridge, 0, sizeof(isbridge)); memset(newgraph, 0, sizeof(newgraph)); memset(newdegree, 0, sizeof(newdegree)); memset(low, 0, sizeof(low)); memset(bccgroup, 0, sizeof(bccgroup)); memset(dfstime, 0, sizeof(dfstime)); for(int i=0, x, y; i<m; ++i)="" {="" 그래프를="" 입력받아="" 인접="" 행렬을="" 생성합니다.="" scanf("%d="" %d",="" &x,="" &y);="" ++x;="" ++y;="" w[x][y]="w[y][x]" }="" dfs를="" 통해="" 절선을="" 구합니다.="" time="bcc" dfs(1);="" for(int="" i="1;"><=n; ++i) if(!bccgroup[i]) { // bfs 를 통해 절선을 거치지 않고 갈 수 있는 점들을 하나의 bcc로 만듭니다. bccgroup[i] = ++bcc; qb = qf = 0; que[qb++] = i; while(qb != qf) { int u = que[qf++]; for(int v=1; v<=n; ++v) if(w[u][v] && !isbridge[u][v] && !bccgroup[v]) { bccgroup[v] = bcc; que[qb++] = v; } } } // 이중 연결 요소 (1..bcc)를 이용한 새로운 그래프를 만듭니다 for(int i=1; i<=n; ++i) for(int j=i+1; j<=n; ++j) { if(w[i][j] && bccgroup[i] != bccgroup[j]) { newgraph[ bccgroup[i] ][ bccgroup[j] ] = 1; newgraph[ bccgroup[j] ][ bccgroup[i] ] = 1; } } // terminal node 를 세기 위해, degree 를 셉니다. for(int i=1; i<=bcc; ++i) for(int j=i+1; j<=bcc; ++j) { if(newgraph[i][j]) { newdegree[i] ++; newdegree[j] ++; } } // terminal nodes int terminal = 0; for(int i=1; i<=bcc; ++i) if(newdegree[i] == 1) terminal++; if(terminal == 1) printf("%d\n", 0); else printf("%d\n", (terminal + 1) / 2); } return 0; }