[IOI2012 Day1] Rings 해법

문제 ↓

rings.pdf

문제의 고리를 노드로 고리끼리 연결이 되면 간선으로 연결을 해주어 그래프로 표현할 수 있다.
문제의 해법에 접근하기 위해서는 다음과 같은 사실들을 관찰할 필요가 있다.

• 만약 차수가 4 이상인 노드가 존재하면, 다른 노드들은 중요한 고리가 될 수 없다. 다른 노드를 제거하면 차수가 3이상인 노드가 남기 때문이다. 같은 의미로 차수가 4이상인 노드가 여러 개면 중요한 고리는 존재하지 않는다.
  
• 만약 차수가 3인 노드 $V$가 존재하면, 모든 중요한 고리는 $V$ 혹은 $V$에 연결된 노드들 중에 있다.
• 만약 싸이클이 존재하면, 모든 중요한 고리는 싸이클 안에 있다.
• 만약 그래프가 여러 개의 직선으로 구성되어 있으면, 모든 고리가 중요한 고리다.

위 사실들을 이용하여 중요한 고리의 개수를 O(1) 만에 구할 수 있다. 차수가 3인 노드가 존재할 때와 존재하지 않을 때 나누어서 코딩하면 편하다. 차수가 3인 노드가 존재할 때에는 중요한 고리가 될 수 있는 후보 4개에 대해 각각 그 노드가 없을 때에 대해 코딩을 해주면 된다.

#include <vector> using namespace std; #define MAXN 1000006 #define mp make_pair #define pb push_back #define sz(v) ((int)(v).size()) typedef pair<int,int> pii; static int N,deg[MAXN],par[MAXN],size[MAXN]; static int _par[4][MAXN],_deg[4][MAXN],_target[4]; static int cycle_cnt,cycle_size; static bool sw,_valid[4]; static vector<pii> edges; int find(int n,int p[MAXN]=par){ return p[n]==n?n:(p[n]=find(p[n],p)); } void Init(int n) { int i; N = n; for (i=1;i<=N;i++) par[i] = i, size[i] = 1; } void addEdge(int a,int b) { int i; for (i=0;i<4;i++){ if (_target[i] == a || _target[i] == b) continue; if (++_deg[i][a] == 3) _valid[i] = 0; if (++_deg[i][b] == 3) _valid[i] = 0; int p = find(a,_par[i]), q = find(b,_par[i]); if (p == q) _valid[i] = 0; _par[i][q] = p; } } void reg(int n) { int i,j,k=0; _target[k++] = n; for (i=0;i<sz(edges);i++){ if (edges[i].first == n) _target[k++] = edges[i].second; if (edges[i].second == n) _target[k++] = edges[i].first; } for (i=0;i<4;i++){ _valid[i] = 1; for (j=1;j<=N;j++) _par[i][j] = j; } for (i=0;i<sz(edges);i++) addEdge(edges[i].first,edges[i].second); } void Link(int a,int b) { a++; b++; deg[a]++; deg[b]++; edges.pb(mp(a,b)); if (!sw && deg[a] == 3) sw = 1, reg(a); else if (!sw && deg[b] == 3) sw = 1, reg(b); else if (!sw){ a = find(a); b = find(b); if (a == b){ cycle_cnt++; cycle_size = size[a]; }else{ par[b] = a; size[a] += size[b]; } }else{ addEdge(a,b); } } int CountCritical() { if (cycle_cnt > 1) return 0; if (!sw){ if (cycle_cnt) return cycle_size; return N; } int ret = 0,i; for (i=0;i<4;i++) ret += _valid[i]; return ret; }