DSU_Exercise

//非路径压缩
int find_1(int x)
{
    int r = x;
    while(pre[r]!=r)
    {
        r = pre[r]; 
    }
    return r;
}
//路径压缩
int find(int x)
{
    if(pre[x]==x)
        return x;
    else
    {
        return pre[x] = find(pre[x]);
    }
}
void join(int x,int y)
{
    int fx = find(x),fy = find(y);
    if(x!=fy)
        pre[fx] = fy;
}

#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdlib>

using namespace std;
typedef long long ll;
const int N = 1010;

int pre[N];
int n,m;
//非路径压缩
int find_1(int x)
{
    int r = x;
    while(pre[r]!=r)
    {
        r = pre[r]; 
    }
    return r;
}
//路径压缩
int find(int x)
{
    if(pre[x]==x)
        return x;
    else
    {
        return pre[x] = find(pre[x]);
    }
}
void join(int x,int y)
{
    int fx = find(x),fy = find(y);
    if(x!=fy)
        pre[fx] = fy;
}
int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        cin>>n>>m;
        for(int i =1;i<=n;++i)
            pre[i] = i;
        for(int i=1;i<=m;++i)
        {
            int x,y;
            cin>>x>>y;
            join(x,y);
        }
        int ans = 0;
        for(int i =1;i<=n;++i)
            if(pre[i]==i)
                ans++;
        cout<<ans<<endl;
    }
    system("pause");
    return 0;
}

#include<iostream>
#include<algorithm>
#include<cstring>

using namespace std;
typedef long long ll;
const ll N = 1010;
ll pre[N];
ll n,m;
ll find(ll x)
{
    if(pre[x]==x)
        return x;
    else
    {
        return pre[x] = find(pre[x]);
    }
    
}
void join(ll x,ll y)
{
    ll fx = find(x),fy = find(y);
    if(x!=fy)
        pre[fx] = fy;
}
int main()
{
    while(cin>>n>>m&&n!=0)
    {
        for(int i =1;i<=n;++i)
            pre[i]=i;
        for(int i =1;i<=m;++i)
        {
            ll x,y;
            cin>>x>>y;
            join(x,y);
        }
        ll ans = 0;
        for(int i =1;i<=n;++i)
        {
            if(pre[i]==i)
                ans++;
        }
        cout<<(ans-1)<<endl;
    }
    system("pause");
    return 0;
}

#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdlib>

using namespace std;
typedef long long ll;
const int N = 100010;
int vis[N];//判断结点是否都被访问
int pre[N];
int n,m;
int t;//判断是否是连通图
//非路径压缩
int find_1(int x)
{
    int r = x;
    while(pre[r]!=r)
    {
        r = pre[r]; 
    }
    return r;
}
//路径压缩
int find(int x)
{
    if(pre[x]!=x)
    {
        pre[x] = find(pre[x]);
    }
    return pre[x];
}
void join(int x,int y)
{
    x = find(x),y = find(y);
    if(x==y) 
        t = 1;
    else pre[x] = y;
}

int main()
{
 
    while(cin>>n>>m)
    {   
        int num = 0;
        t = 0;
        for(int i =1;i<N;++i)
            pre[i] = i,vis[i] = 0;
        if(n==-1&&m==-1)
            break;
        if(n==0&&m==0)
        {
            puts("Yes");
            continue;
        }
        while(n)
        {
            if(t==0)
                join(n,m),vis[n] = vis[m] = 1;
            cin>>n>>m;
        }
        for(int i =1;i<N;++i)
        {
            if(vis[i]&&pre[i]==i)
                num++;
        }
        
        if(num==1&&t==0)
            puts("Yes");
        else
        {
            puts("No");
        }
        
    }
    system("pause");
    return 0;
}

#include<cstdio>
#include<cstring>
#define N 100001
int father[N],mark[N],flag,edges;
int find(int x)
{
    if(x==father[x])
        return x;
    else
        return father[x] = find(father[x]);
}
 
void Union(int x,int y)
{
    int a=find(x);
    int b=find(y);
    if(a==b)
    {
        flag=1;
        return;
    }
    mark[a]=1;
    mark[b]=1;
    edges++;
    father[b]=a;
}
int main()
{
    
    int a,b,c,d,i,m,cas=1;
    while(1)
    {
        scanf("%d%d",&a,&b);
        if(a<0&&b<0)break;

        if(a==0&&b==0) 
        {
            printf("Case %d is a tree.\n",cas++);
            continue;
        }
        flag=edges=m=0;
        memset(mark,0,sizeof(mark));
        
        for(i=1;i<=N;i++)
            father[i]=i;
        
        Union(a,b);
        while(scanf("%d%d",&c,&d)!=EOF)
        {
            if(c==0&&d==0)
                break;
            if(c==d||father[d]!=d)
                flag=1;  //注意这里，不能指向自身，只能有一个父亲。
            Union(c,d);
        }
        if(flag) {printf("Case %d is not a tree.\n",cas++);continue;}
        for(i=1;i<=N;i++)
        {
            if(mark[i]) m++;
        }
       
        
        if(m==edges+1)
        {
            printf("Case %d is a tree.\n",cas++);
        }
        else printf("Case %d is not a tree.\n",cas++);
    }
    return 0;
}