链接

[]

题意

n个人参加宴席，有m个信息表示a与b认识，认识有传递性，

问最后该安排多少卓使得只有相互认识的在一起吃饭。

分析

裸的带路径压缩的并查集

代码

#include
    
     #include
     
      using namespace std;int n,m;int f[1010];int r[1010];void init(){    for(int i=1;i<=n;i++)    f[i]=i;}void k(){    for(int i=1;i<=n;i++)    r[i]=1;}int find(int x){    if(f[x]==x) return x;    else{        f[x]=find(f[x]);        return f[x];    }}void unionSet(int x, int y) {    if ((x = find(x)) == (y = find(y))) return;    if (r[x] > r[y]) f[y] = x;    else {        f[x] = y;        if (r[x] == r[y]) r[y]++;    }}int main(){    int T,a,b;    //freopen("in.txt","r",stdin);    cin>>T;    while(T--){        cin>>n>>m;        init();        k();        for(int i=1;i<=m;i++){            cin>>a>>b;            unionSet(a,b);        }         int sum=0;        for(int i=1;i<=n;i++)        if(f[i]==i) sum++;        cout<
      
       <