围巾的纠结(并查集之非完整集合的子集合是否连成圈的问题)

骑猪看日落 2022-08-07 10:51 141阅读 0赞

<table style="border-collapse:collapse; border-spacing:0px; border:1px solid rgb(206,225,238); margin:20px auto 0px; width:790px; color:rgb(0,0,0); text-align:center; background:rgb(240,245,248)"> 
 <tbody> 
 <tr style="padding:0px"> 
 <td style="padding:30px 10px; color:rgb(26,92,200); font-family:'Times New Roman'; font-size:32px; font-weight:bold"> 围巾的纠结</td> 
 </tr> 
 <tr style="padding:0px"> 
 <td style="padding:3px 10px"> 
 <table style="border-collapse:collapse; border-spacing:0px; border:0px; margin:0px auto; color:green; font-size:10pt"> 
 <tbody> 
 <tr style="padding:0px"> 
 <td style="padding:3px 10px">Time Limit: 500 MS</td> 
 <td style="padding:3px 10px">Memory Limit: 32768 K</td> 
 </tr> 
 </tbody> 
 </table> 
 <table style="border-collapse:collapse; border-spacing:0px; border:0px; margin:0px auto; color:green; font-size:10pt"> 
 <tbody> 
 <tr style="padding:0px"> 
 <td style="padding:3px 10px">Total Submit: 69(36 users)</td> 
 <td style="padding:3px 10px">Total Accepted: 34(32 users)</td> 
 <td style="padding:3px 10px">Rating:&nbsp;<img src="http://acm.hrbust.edu.cn/Public/images/star-solid.png" alt="" style="border:0px; margin:0px; padding:0px"></td> 
 <td style="padding:3px 10px">Special Judge:&nbsp;No</td> 
 </tr> 
 </tbody> 
 </table> </td> 
 </tr> 
 <tr style="padding:0px"> 
 <td style="padding:10px; color:rgb(124,169,237); font-family:Arial; font-size:18px; font-weight:bold; text-align:left; width:770px"> Description</td> 
 </tr> 
 <tr style="padding:0px"> 
 <td style="padding:10px; font-family:'courier new',courier,monospace; font-size:13px; text-align:left; table-layout:fixed; width:770px; word-break:break-all; word-wrap:break-word"> 小破想要织一条围巾，可是她并不擅长于织围巾。由于工作太忙，每天她都只能织一点。为了快速的织完围巾，她决定直接把毛线球连在一起。围巾上有球球还是非常可爱的嘛~ &nbsp; &nbsp;&nbsp;于是小破去商店买了n个毛线球。每天晚上睡觉之前，她就抽出一点时间，把其中两个原本分开的毛线球织在一起。由于是睡觉之前干活，人太困了，过了m天之后，她发现自己完全织乱了，于是她决定拆掉重织。可是由于她的织法过于特殊，她发现，一旦几个毛线球被织成了一个圈，就不能完好的解开了。现在她想知道，她还能把这条"围巾"还原吗？</td> 
 </tr> 
 <tr style="padding:0px"> 
 <td style="padding:10px; color:rgb(124,169,237); font-family:Arial; font-size:18px; font-weight:bold; text-align:left; width:770px"> Input</td> 
 </tr> 
 <tr style="padding:0px"> 
 <td style="padding:10px; font-family:'courier new',courier,monospace; font-size:13px; text-align:left; table-layout:fixed; width:770px; word-break:break-all; word-wrap:break-word"> 多组测试数据 每组测试数据第一行有两个整数n,m(1 &lt;= n &lt;= 10000, 1 &lt;= m &lt;= 1000000) 接下来有m行，每行有两个数a,b，表示将a和b号毛球织到一起。 </td> 
 </tr> 
 <tr style="padding:0px"> 
 <td style="padding:10px; color:rgb(124,169,237); font-family:Arial; font-size:18px; font-weight:bold; text-align:left; width:770px"> Output</td> 
 </tr> 
 <tr style="padding:0px"> 
 <td style="padding:10px; font-family:'courier new',courier,monospace; font-size:13px; text-align:left; table-layout:fixed; width:770px; word-break:break-all; word-wrap:break-word"> 对于每组测试数据，如果她能还原，则输出"YES"， 否则输出"NO"</td> 
 </tr> 
 <tr style="padding:0px"> 
 <td style="padding:10px; color:rgb(124,169,237); font-family:Arial; font-size:18px; font-weight:bold; text-align:left; width:770px"> Sample Input</td> 
 </tr> 
 <tr style="padding:0px"> 
 <td style="padding:10px; font-family:'courier new',courier,monospace; font-size:13px; text-align:left; table-layout:fixed; width:770px; word-break:break-all; word-wrap:break-word"> 5 4 1 2 2 3 3 1 1 4 5 4 1 2 2 3 3 4 4 5 </td> 
 </tr> 
 <tr style="padding:0px"> 
 <td style="padding:10px; color:rgb(124,169,237); font-family:Arial; font-size:18px; font-weight:bold; text-align:left; width:770px"> Sample Output</td> 
 </tr> 
 <tr style="padding:0px"> 
 <td style="padding:10px; font-family:'courier new',courier,monospace; font-size:13px; text-align:left; table-layout:fixed; width:770px; word-break:break-all; word-wrap:break-word"> NO YES </td> 
 </tr> 
 <tr style="padding:0px"> 
 <td style="padding:10px; color:rgb(124,169,237); font-family:Arial; font-size:18px; font-weight:bold; text-align:left; width:770px"> Source</td> 
 </tr> 
 </tbody> 
</table>

这一题目有一个细节就是你要注意m天不一定就织完了n个

球，所以我们做的应该是判断m天之内的球是否有连成一个圈

的情况发生！

#include<stdio.h>
 #include<string.h>
 int a[10009];
 int Find(int x)
 {
 int r=x;
 while(r!=a[r])
 r=a[r];
 
 /* int i=x,j;
 while(a[i]!=r)
 {
 j=a[i];
 a[i]=r;
 i=j;
 }*/
 return r;
 }//这个就是找老大的函数，什么时候停止？就是当一个人的老大是他自己的时候！
 void mix(int x,int y)
 {
 int fx=Find(x),fy=Find(y);//首先要找到他们各自的老大
 if(fx!=fy)//如果他们的老大不相等，要合并就必须其中的一个老大向另外一个老大称老大
 {
 a[fy]=fx;
 // sum++;
 }
 }
 int main()
 {
 int n,m,i,j,c,d,flag;
 while(scanf("%d%d",&n,&m)!=EOF)
 {
 flag=0;
 memset(a,0,sizeof(a));
 for(i=1;i<=n;i++)
 {
 a[i]=i;
 }
 for(j=1;j<=m;j++)
 {
 scanf("%d%d",&c,&d);
 int fx=Find(c);int fy=Find(d);//首先要找到他们各自的老大
 // printf("%d %d\n",fx,fy);
 if(fx==fy)//如果他们的老大不相等，要合并就必须其中的一个老大向另外一个老大称老大
 {
 flag=1;
 }
 else
 {
 a[fx]=fy;
 }
 //mix(c,d);
 }
 // printf("%d\n",sum);
 if(flag==0)
 {
 printf("YES\n");
 }
 else
 {
 printf("NO\n");
 }
 }
 }

好吧，那你肯定又问了，既然与n没有关系，能不能判断m天之内

的情况呢？答案是肯定的，只要m天之内的子集合没有练成一个圈

不就可以了吗？嘿嘿，确实是这样的！下面发一下代码！

#include<stdio.h>
 #include<string.h>
 int a[10009],sum;
 int Find(int x)
 {
 int r=x;
 while(r!=a[r])
 r=a[r];
 
 /* int i=x,j;
 while(a[i]!=r)
 {
 j=a[i];
 a[i]=r;
 i=j;
 }*/
 return r;
 }//这个就是找老大的函数，什么时候停止？就是当一个人的老大是他自己的时候！
 void mix(int x,int y)
 {
 int fx=Find(x),fy=Find(y);//首先要找到他们各自的老大
 if(fx!=fy)//如果他们的老大不相等，要合并就必须其中的一个老大向另外一个老大称老大
 {
 a[fy]=fx;
 // sum++;
 }
 }
 int main()
 {
 int n,m,i,j,c,d;
 while(scanf("%d%d",&n,&m)!=EOF)
 {
 sum=0;
 memset(a,0,sizeof(a));
 for(i=1;i<=n;i++)
 {
 a[i]=i;
 }
 for(j=1;j<=m;j++)
 {
 scanf("%d%d",&c,&d);
 int fx=Find(c);int fy=Find(d);//首先要找到他们各自的老大
 // printf("%d %d\n",fx,fy);
 if(fx!=fy)//如果他们的老大不相等，要合并就必须其中的一个老大向另外一个老大称老大
 {
 a[fx]=fy;
 sum++;
 }
 //mix(c,d);
 }
 // printf("%d\n",sum);
 if(sum==m)
 {
 printf("YES\n");
 }
 else
 {
 printf("NO\n");
 }
 }
 }