题目要求 : 判断所给的图是否连同并且是否存在环

并查集做这一个题实在是再好不过了 , 是否连同可以看有几个顶点 , 是否存在环 , 看看是否有一条边的两个定点的祖先节点是一个点 . 下面附上渣渣代码

1 #include
     
       2 #include
      
        3 #include
       
         4 #include
        
          5 #include
         
           6 #include
          
            7 #include
           
             8 #include
            
              9 #include
             
              10 #include
              
               11 #include
               
                12 #include
                13 #include
                 
                  14 using namespace std;15 int father[100005],visited[100005],sum,flag;16 int find(int x) // 做了时间上的优化 ,但是 在空间复杂度上比较高17 {18 if(x!=father[x])19 father[x]=find(father[x]);20 sum++;21 return father[x];22 }23 void merge(int x,int y) // 做了时间复杂度上的优化 让并查集的 深度尽量 浅24 {25 int sum1,sum2;26 sum=0;27 x=find(x);28 sum1=sum; // x 的深度29 sum=0;30 y=find(y);31 sum2=sum; // y 的深度32 if(x!=y)33 {34 if(sum1>sum2)35 father[y]=x;36 else37 father[x]=y;38 }39 else40 flag=1; // 同一条边 的 两个父节点相同 , 则成环了41 }42 int main() // 所有的 房间应该还是 连通的43 {44 int n,m;45 while(scanf("%d%d",&n,&m)) // 不能 存在 环46 {47 flag=0;48 if(n==m&&n==-1)49 break;50 if(n==m&&n==0)51 {52 printf("Yes\n");53 continue;54 }55 for(int i=0;i<100005;i++)56 {57 father[i]=i; // i 的 爸爸 还是 i58 visited[i]=0; // 初始化 访问标记59 }60 visited[n]=visited[m]=1; // 这两个点 标记以访问61 merge(n,m); // 这个两个点 先构树62 while(scanf("%d%d",&n,&m))63 {64 if(n==m&&n==0)65 break;66 merge(n,m);67 visited[n]=visited[m]=1;68 }69 int count1=0;70 for(int i=0;i<100005;i++)71 {72 if(visited[i]&&father[i]==i)73 count1++;74 if(count1>1)75 {76 flag=1;77 break;78 }79 }80 if(flag)81 printf("No\n");82 else83 printf("Yes\n");84 }85 return 0;86 }