[AtCoder] ABC 177 D – Friends
問題
方針
友達同士のグループの人数の最大値の分だけグループがあれば、「同じグループの中に友達がいない」という状況がつくれます。したがって、連結成分の最大値を求めます。これは、幅優先探索や Union-Find を使うことで求めることができます。
コード
幅優先探索
#include <bits/stdc++.h> using namespace std; typedef long long ll; int main() { int N, M; cin >> N >> M; int A[M], B[M]; set<int> adj[N]; for (int i = 0; i < M; i++) { cin >> A[i] >> B[i]; A[i]--; B[i]--; adj[A[i]].insert(B[i]); adj[B[i]].insert(A[i]); } int d = 0; bool flag[N]{}; for (int i = 0; i < N; i++) { if (flag[i]) continue; int k = 1; flag[i] = true; deque<int> q; q.push_back(i); while (!q.empty()) { int u = q.front(); q.pop_front(); for (int j : adj[u]) { if (!flag[j]) { q.push_back(j); k++; flag[j] = true; } } } d = max(d, k); } cout << d << "\n"; return 0; }
Union-Find
#include <bits/stdc++.h> using namespace std; typedef long long ll; // Union-Find class DisjointSet { public: vector<int> p, rank, size; int group_num; DisjointSet(int n) { p.assign(n, 0); rank.assign(n, 0); size.assign(n, 0); group_num = n; for (int i = 0; i < n; i++) { make_set(i); } } void make_set(int x) { p[x] = x; rank[x] = 0; size[x] = 1; } bool same(int x, int y) { return find_set(x) == find_set(y);; } int find_set(int x) { if (x != p[x]) { p[x] = find_set(p[x]); } return p[x]; } int union_size(int x) { if (x != p[x]) { size[x] = union_size(find_set(x)); } return size[x]; } void link(int x, int y) { if(rank[x] > rank[y]) { p[y] = x; size[x] = size[x] + size[y]; }else if(rank[x] < rank[y]){ p[x] = y; size[y] = size[x] + size[y]; }else if(x != y) { p[y] = x; rank[x]++; size[x] = size[x] + size[y]; } } void unite(int x, int y) { if (find_set(x) != find_set(y)) group_num--; link(find_set(x), find_set(y)); } }; int main() { int N, M; cin >> N >> M; int A[M], B[M]; DisjointSet ds(N); for (int i = 0; i < M; i++) { cin >> A[i] >> B[i]; A[i]--; B[i]--; ds.unite(A[i], B[i]); } int d = 0; for (int i = 0; i < N; i++) { d = max(d, ds.union_size(i)); } cout << d << "\n"; return 0; }
ディスカッション
コメント一覧
素人質問で申し訳ないのですが、
幅優先探索のコードで11-12行で後置デクリメントを行っている理由はなんですか?
コメントありがとうございます。
この問題では人1から人Nまでいます。これは、1ベースなので、0ベースとするためにデクリメントを行っています。
例えば、adj[0] は人0と友達であるリストを表しています。
迅速な対応ありがとうございます。