POJ 1611 The Suspects——并查集

POJ 1611 The Suspects——并查集

建立集合看看那些人和0号人在一个集合中就可以

#include #include #include #include using namespace std;const int MAXN = 5 * 1e4;int par[MAXN], ran[MAXN];int N, M;void Init() { for (int i = 0; i < N; i++) par[i] = i, ran[i] = 0;}int Query(int x) { return (x == par[x]) ? x : par[x] = Query(par[x]);}void Union(int x, int y) { x = Query(x), y = Query(y); if (x == y) return; if (ran[x] < ran[y]) { par[x] = y; } else { par[y] = x; if (ran[x] == ran[y]) ran[x]++; }}int main() { while (~scanf("%d %d", &N, &M) && (N + M)) { Init(); int cnt, t1, t2; for (int i = 1; i <= M; i++) { scanf("%d", &cnt); scanf("%d", &t1); for (int j = 2; j <= cnt; j++) { scanf("%d", &t2); Union(t1, t2); } }// for (int i = 0; i < 20; i++) cout << par[i] << " ";// cout << endl; int ans = 0; int temp = Query(0); for (int i = 1; i < N; i++) { if (Query(i) == temp) ans++; } printf("%d\n", ans + 1); } return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。