首页 > 代码库 > How Many Tables-并查集
How Many Tables-并查集
Time Limit: 1000MS | Memory Limit: 32768KB | 64bit IO Format: %I64d & %I64u |
Description
One important rule for this problem is that if I tell you A knows B, and B knows C, that means A, B, C know each other, so they can stay in one table.
For example: If I tell you A knows B, B knows C, and D knows E, so A, B, C can stay in one table, and D, E have to stay in the other one. So Ignatius needs 2 tables at least.
Input
Output
Sample Input
2 5 3 1 2 2 3 4 5 5 1 2 5
Sample Output
2 4题目目的非常easy就是让你求有几个集合所以直接模板飘过/* Author: 2486 Memory: 1420 KB Time: 0 MS Language: G++ Result: Accepted */ #include <cstring> #include <string> #include <cstdio> #include <cmath> #include <algorithm> using namespace std; const int maxn=1000+5; int a,b,T,N,M,par[maxn],ranks[maxn]; void init(int sizes) { for(int i=1; i<=sizes; i++) { par[i]=i; ranks[i]=1; } } int find(int x) { return par[x]==x?x:par[x]=find(par[x]); } bool same(int x,int y) { return find(x)==find(y); } void unite(int x,int y) { x=find(x); y=find(y); if(x==y)return ; if(ranks[x]>ranks[y]) { par[y]=x; } else { par[x]=y; if(ranks[x]==ranks[y])ranks[x]++; } } int main() { scanf("%d",&T); while(T--) { scanf("%d",&N); scanf("%d",&M); init(N); for(int i=0; i<M; i++) { scanf("%d%d",&a,&b); unite(a,b); } int ans=0; for(int i=1; i<=N; i++) { if(par[i]==i)ans++; } printf("%d\n",ans); } return 0; }
How Many Tables-并查集