Think: 还是并查集的题目，因为有路就有岛，所以只要判断是否为0即可。
PRoblem Description 海上有N(1<= N <=2000)个岛，编号从1到N,同一部落的岛屿之间有直接或间接的路相连，不同部落之间无路可通。现在给出M(1<= M <= N*(N-1)/2)条路。问这片海域上共有多少部落。 Input 多组输入。每组第一行输入N，M。接下来M行每行，每行两个整数u,v代表岛u与v之间有一条路。 Output 每组数据输出一个整数，代表部落数。 Example Input
3 1 1 2 3 2 1 2 1 3
Example Output
2 1
#include<bits/stdc++.h>using namespace std;int root(int x);void Merge(int a, int b);int pre[2024];int cnt[2024];int main() { int N, M; int i, sum; int a, b; while(cin >> N >> M) { sum = 0; memset(cnt, 0, sizeof(cnt)); for (i = 1;i <= N; i++) pre[i] = i; for (i = 1;i <= M;i ++) { cin >> a >> b; Merge(a, b); } for (i = 1;i <= N;i ++) { cnt[root(i)] ++; } for (i = 1;i <= N;i ++) { if (cnt[i] != 0) sum ++; } cout << sum << endl; } return 0; } int root(int x) { while(x != pre[x]) { x = pre[x]; } return x; } void Merge(int a, int b) { if (root(a) != root(b)) { pre[root(a)] = root(b); } return ; }/***************************************************User name: Result: AcceptedTake time: 28msTake Memory: 184KBSubmit time: 2017-02-21 16:10:59****************************************************/新闻热点
疑难解答
