当前位置: 代码迷 >> 综合 >> 大家快来A水题 oj
  详细解决方案

大家快来A水题 oj

热度:89   发布时间:2024-01-14 22:47:57.0

大家快来A水题

Time Limit: 1000MS Memory Limit: 65536KB
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
Hint
Author
#include <stdio.h>
int a[10000001];
int find(int x)
{while(x != a[x]){x = a[x];}return x;
}
void marge(int x,int y)
{int fx,fy;fx = find(x);fy = find(y);if(fx != fy)a[fx] = fy;
}
int main()
{int n,m,i,u,v;while(scanf("%d%d",&n,&m) != EOF){for(i = 1;i <= n;i++){a[i] = i;}for(i = 0;i < m;i++){scanf("%d%d",&u,&v);marge(u,v);}int count = 0;for(i = 1;i <= n;i++){if(a[i] == i)count++;}printf("%d\n",count);}return 0;
}
 
  相关解决方案