2개의 댓글이 있습니다.
-
-
hyunhwan -
PKU 3177번 문제가 아마 biconnected component 문제였는데, 예전에 이걸 못풀다가 솔루션을 찾았었는데 도움이 되실련지는 모르겠네요. 일단 첨부해봅니다.
#include <iostream> #include <fstream> #include <algorithm> #include <climits> #include <cassert> #include <vector> #include <cstddef> #include <stack> using namespace std; #define MAXC 5000 #define MAXR 10000 struct road { int target; int dual; road() {} road(int _target, int _dual) : target(_target), dual(_dual) {} }; struct castle { int id; int top; int parent; int bcc; vector<road> roads; castle() : id(-1), top(-1), parent(-1), bcc(-1), roads() {} }; static int C; static castle castles[MAXC]; static bool connected() { stack<int> todo; vector<bool> seen(C, false); int remain = C; todo.push(0); seen[0] = true; while (!todo.empty()) { int cur = todo.top(); todo.pop(); remain--; seen[cur] = true; for (size_t i = 0; i < castles[cur].roads.size(); i++) { int nxt = castles[cur].roads[i].target; if (!seen[nxt]) { todo.push(nxt); seen[nxt] = true; } } } return remain == 0; } static void readin() { int R, x, y; cin >> C >> R; assert(3 <= C && C <= MAXC); assert(C - 1 <= R && R <= MAXR); for (int i = 0; i < R; i++) { cin >> x >> y; assert(x != y); assert(1 <= x && x <= C); assert(1 <= y && y <= C); x--; y--; castles[x].roads.push_back(road(y, castles[y].roads.size())); castles[y].roads.push_back(road(x, castles[x].roads.size() - 1)); } assert(connected()); } static int recurse(int cur, int up_edge) { static int id_pool = 0; static stack<int> bcc; int leaves = 0; castles[cur].id = id_pool++; castles[cur].top = cur; bcc.push(cur); for (size_t i = 0; i < castles[cur].roads.size(); i++) { int nxt = castles[cur].roads[i].target; if ((int) i == up_edge) continue; if (castles[nxt].id == -1) { castles[nxt].parent = cur; leaves += recurse(nxt, castles[cur].roads[i].dual); } if (castles[castles[nxt].top].id < castles[castles[cur].top].id) castles[cur].top = castles[nxt].top; } if (castles[cur].top == cur) { while (bcc.top() != cur) { castles[bcc.top()].bcc = cur; bcc.pop(); } castles[cur].bcc = cur; bcc.pop(); if (leaves == 0) leaves = 1; } return leaves; } static bool bridge(int c, int edge) { return castles[c].top == c && castles[c].roads[edge].target == castles[c].parent; } static int solve() { int leaves = recurse(0, -1); int root_children = 0; for (int i = 1; i < C; i++) { int p = castles[i].parent; if (castles[i].top == i && castles[p].bcc == 0) root_children++; } if (root_children == 0) return 0; else if (root_children == 1) leaves++; return (leaves + 1) / 2; } int main() { readin(); cout << solve() << "\n"; return 0; }
15년 전 link
-
-
정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.
wookayin
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 두 가지로 나뉘게 됩니다. 그렇다면