蓝桥杯2017年第八届真题-发现环 （C语言代码）------------C语言——菜鸟级

解题思路:

并查集 找环 未成环之前 看作一个树 

  用并查集找到环 两点 找的同时 建立一个 并查集树（自己瞎起的）找到两点后

   从两个点分别回到并查集的根节点经过的点标记上 这两个点单独经过的点（交点处除外）都是环上点 

  原文  欢迎访问 我的博客

注意事项:

参考代码:

#include<stdio.h>
#include<string.h>
#define N 1000002 
typedef long long ll;
ll a[N][3],f[N],bj[N],jd[N];
//ll BCJ(ll s)//并查集找根和更新 
//{  return f[s]==0?s:f[s]=BCJ(f[s]);
//}
ll BCJ(ll s)
{
 ll tem ,tx=s;
 while(f[tx]!=0)tx=f[tx];//并查集找根
 while(s!=tx)//并查集更新 
 { tem=f[s];
    f[s]=tx;
    s=tem;
 }
 return tx;
}
void BCJtree(ll x1,ll x2)//建立并查集树 
{
ll tx=x2,next=x1,last=jd[x1]; //两树合并  父变子 子变父 
while(next!=0)
{
jd[next]=tx;
tx=next;
next=last;
    last=jd[next];
}
}
void xzh(ll x)//寻找环节点 
{ ll last,r=x;bj[x]+=1;
while(1)
{if(jd[x]==0||bj[x]==2)break;//到并查集根节点或有重复节点 跳出 
  last=jd[x];
  bj[last]+=1;
  x=last;
}
if(bj[x]==2)// 重复节点 消重和去多余节点 
{ bj[x]=1;
  while(jd[x]!=0)
  {last=jd[x];
   bj[last]=0;
   x=last;
  }
}
}
 int main()
 { ll i,j,s1,s2,n,flag;
    while(scanf("%lld",&n)!=EOF)
    {  flag=0;
    memset(f,0,sizeof(f));
        memset(bj,0,sizeof(bj));
        memset(jd,0,sizeof(jd));
    for(i=1;i<=n;i++)
     { scanf("%lld%lld",&a[i][0],&a[i][1]);
        if(!flag)
        {  
        s1=BCJ(a[i][0]);
         s2=BCJ(a[i][1]);
        if(s1==s2)flag=i;//如果之前已经是同集合 这为环上两点 标记 
        else 
{
 if(!f[a[i][0]]) f[s1]=s2,BCJtree(a[i][0],a[i][1]);//a[i][0]节点为单集合或作为根节点的集合 
  else  f[s2]=s1,BCJtree(a[i][1],a[i][0]);// 含a[i][1]的集合接在含a[i][0]的集合 
  
}
        }
        
     }
    xzh(a[flag][0]);//从 A节点开始走 
    xzh(a[flag][1]);//从 B节点开始走 
      for(i=1;i<=n;i++) 
    if(bj[i]==1)printf("%lld ",i);
    printf("\n"); 
    }
 return 0;
 }