POJ1611: The Suspects
問題
問題文
http://poj.org/problem?id=1611
問題概要
n 人の学生とその学生からなる m
個のグループが与えられる。
全ての学生に 0 ~ n−1 の番号が振られており 0 番目の学生に SARS という病気の感染の疑いがある。感染の疑いのある学生と同じグループの学生にも感染の疑いがあるとする。
感染の疑いのある学生の人数を求めよ。
例
次のような入力が与えられたとき
100 4 2 1 2 5 10 13 11 12 14 2 0 1 2 99 2 200 2 1 5 5 1 2 3 4 5 1 0 0 0
1 つ目の入力は n = 100, m = 4 で
1 番目の学生は 0 番目の学生と同じグループであるから感染の疑いがあり, 1 番目の学生と同じグループである 2番目の学生, その 2 番目の学生と同じグループである 99 番目の学生も感染の疑いがあるので答えは 4 となる。
同様に 2 つ目の入力の答えは 1, 3 つ目も 1 となるので
4 1 1
が出力すべき答えである。
解答例
指針
- 頂点 0 が属する連結成分のサイズを求める。
解説
学生のグループを連結グラフとみなすと求めるものは頂点 0 が属する連結成分のサイズとなる。
グラフの連結判定は DFS や BFS などの単純な探索をすることで O(|V| + |E|) で可能である。
Union-Find というデータ構造を用いて解くこともできる。
DFS による解法
以下のような入力に対して
100 4 2 1 2 5 10 13 11 12 14 2 0 1 2 99 2
次のようなグラフを考える。
連結性のみに興味があるのでグループに属する最初の学生とそれ以外の学生を辺でつなげばいい。(他にもつなぎ方は色々ある)
頂点 0 から DFS を行い連結成分のサイズを求める。
- 再帰版
/* Memory: 1304K Time: 79MS Language:C++ */ #include <cstdio> #include <cstring> #include <vector> #include <stack> using namespace std; vector<int> G[30001]; bool visited[30001]; int ans; void dfs(int v){ visited[v] = true; ans++; for (int i = 0; i < G[v].size(); i++) { if (!visited[G[v][i]]) { dfs(G[v][i]); } } } int main() { int n, m, k; int leader, user; while (scanf("%d %d", &n, &m)) { if (!n && !m) { break; } memset(visited, 0, sizeof(visited)); for (int i = 0; i < n; i++) { G[i].clear(); } for (int i = 0; i < m; i++) { scanf("%d %d", &k, &leader); while (--k) { scanf("%d", &user); G[leader].push_back(user); G[user].push_back(leader); } } ans = 0; dfs(0); printf("%d\n", ans); } }
- 明示的に Stack を使った版
このコードの Stack を Queue に変えるだけで BFS になる。
/* Memory: 1348K Time: 94MS Language:C++ */ #include <cstdio> #include <cstring> #include <vector> #include <stack> using namespace std; vector<int> G[30001]; bool visited[30001]; int ans; void dfs(int v) { ans = 0; stack<int> St; St.push(v); visited[v] = true; while (!St.empty()) { int cur = St.top(); St.pop(); ans++; for (int i = 0; i < G[cur].size(); i++) { if (!visited[G[cur][i]]) { St.push(G[cur][i]); visited[G[cur][i]] = true; } } } printf("%d\n", ans); } int main() { int n, m, k; int leader, user; while (scanf("%d %d", &n, &m)) { if (!n && !m) { break; } memset(visited, 0, sizeof(visited)); for (int i = 0; i < n; i++) { G[i].clear(); } for (int i = 0; i < m; i++) { scanf("%d %d", &k, &leader); while(--k) { scanf("%d", &user); G[leader].push_back(user); G[user].push_back(leader); } } dfs(0); } return 0; }
DFS による解法 (二部グラフ)
各グループも頂点とみなした二部グラフを考える。
各グループを 30001 ~ 30501 までの番号をつける。
すなわち以下のような入力に対して
100 4 2 1 2 5 10 13 11 12 14 2 0 1 2 99 2
次のような二部グラフを考える。
頂点 0 から DFS をして 訪れた頂点が 30000 以下のときのみをカウントして答えを求める。
/* Memory: 1312K Time: 94MS Language:C++ */ #include <cstdio> #include <cstring> #include <vector> using namespace std; vector<int> G[30502]; bool visited[30502]; int ans; void dfs(int v){ visited[v] = true; if (v < 30001) { ans++; } for (int i = 0; i < G[v].size(); i++) { if (!visited[G[v][i]]) { dfs(G[v][i]); } } } int main() { int n, m, k, v; while (scanf("%d %d", &n, &m)) { if (!n && !m) { break; } memset(visited, 0, sizeof(visited)); for (int i = 0; i < 30502; i++) { G[i].clear(); } for (int i = 0; i < m; i++) { scanf("%d", &k); while (k--) { scanf("%d", &v); G[i + 30001].push_back(v); G[v].push_back(i + 30001); } } ans = 0; dfs(0); printf("%d\n", ans); } return 0; }
Union-Find による解法
Union-Find とは互いに素な集合に対して以下の 2 つの操作を効率よく行うことが出来るデータ構造である。
Union : 2 つの集合を 1 つに統合する。
Find : 特定の要素がどの集合に属しているか見つける。
Union-Find を使うと実装が楽になる。
/* Memory: 480K Time: 0MS Language: C++ */ #include <cstdio> #include <vector> using namespace std; struct uf_tree { vector<int> par, sizes; uf_tree(int n) : par(n), sizes(n, 1) { for (int i = 0; i < n; i++) { par[i] = i; } } int find(int x) { if (x == par[x]) return x; return par[x] = find(par[x]); } void unite(int x, int y) { x = find(x); y = find(y); if (x == y) return; if (sizes[x] < sizes[y]) { swap(x, y); } par[y] = x; sizes[x] += sizes[y]; } bool same(int x, int y) { return find(x) == find(y); } int size(int x) { return sizes[find(x)]; } }; int main() { int n, m, k, leader, user; while (scanf("%d %d", &n, &m)) { if (!n && !m) { break; } uf_tree uf(n); for (int i = 0; i < m; i++) { scanf("%d %d", &k, &leader); while (--k) { scanf("%d", &user); uf.unite(leader, user); } } printf("%d\n", uf.size(0)); } return 0; }
