并查集待续

2019-04-13 20:33发布

站内文章 / 模拟电子
13633 0 1468
#include
#include
#include
#include
int F[100005];//关系表 
bool flag[100005];//是老大 
///bool fin[100005];
int m,n,ans=0;
using namespace std;
int find(int x)
{
    int B;
    if(F[x]==x){//找到了最终老大 
            B=x;
            ///fin[x]=1;//标记 
    } 
    else{
        find(F[x]);//找老大的老大 
    } 
    return B;//x最终的老大  }
void uni(int x,int y)
{
    if(F[x]!=0&&F[x]==F[x])
    {
        uni(F[x],y);
    }//如果x已有老大，则让原老大F[x]认新的老大 递归的  
       ////if(flag[x]==1){        
       ////}//如果x还有小弟 就让老小弟认新老大  合并？ 
    else
    {   
        F[x]=y; //y给x当老大
        flag[y]=1; //标记 y是老大
    }      
    return ;
}
int main()
{
    freopen("fus.txt","r",stdin); 
    scanf("%d%d",&n,&m);//
    for(int i=1;i<=n;i++){
        F[i]=i;  
    }//初始化 
    int a,b;
    for(int j=1;j<=m;j++){
       scanf("%d %d",&a,&b);
       uni(a,b);    
    }
////////////////////////////////////////////////////// 
    for(int k=1;k<=n;k++)
    {
        find(k);//有重复怎么办 记忆？ 
    }//有几个
    for(int l=1;l<=n;l++)
    {
        if(F[l]==l){ //保留自环是老老大 
            ans++;
        }     
    }//计数 
    printf("%d",ans);
    return 0;    
}        

热门文章