怎么百度做网站,培训机构网站建设,pr,欧美风格企业网站解题思路:并查集 找环 未成环之前 看作一个树用并查集找到环 两点 找的同时 建立一个 并查集树(自己瞎起的)找到两点后从两个点分别回到并查集的根节点经过的点标记上 这两个点单独经过的点(交点处除外)都是环上点原文 欢迎访问 我的博客注意事项:参考代码:#include#include#d…解题思路:并查集 找环 未成环之前 看作一个树用并查集找到环 两点 找的同时 建立一个 并查集树(自己瞎起的)找到两点后从两个点分别回到并查集的根节点经过的点标记上 这两个点单独经过的点(交点处除外)都是环上点原文 欢迎访问 我的博客注意事项:参考代码:#include#include#define N 1000002typedef 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 ,txs;while(f[tx]!0)txf[tx];//并查集找根while(s!tx)//并查集更新{ temf[s];f[s]tx;stem;}return tx;}void BCJtree(ll x1,ll x2)//建立并查集树{ll txx2,nextx1,lastjd[x1]; //两树合并 父变子 子变父while(next!0){jd[next]tx;txnext;nextlast;lastjd[next];}}void xzh(ll x)//寻找环节点{ ll last,rx;bj[x]1;while(1){if(jd[x]0||bj[x]2)break;//到并查集根节点或有重复节点 跳出lastjd[x];bj[last]1;xlast;}if(bj[x]2)// 重复节点 消重和去多余节点{ bj[x]1;while(jd[x]!0){lastjd[x];bj[last]0;xlast;}}}int main(){ ll i,j,s1,s2,n,flag;while(scanf(%lld,n)!EOF){ flag0;memset(f,0,sizeof(f));memset(bj,0,sizeof(bj));memset(jd,0,sizeof(jd));for(i1;in;i){ scanf(%lld%lld,a[i][0],a[i][1]);if(!flag){s1BCJ(a[i][0]);s2BCJ(a[i][1]);if(s1s2)flagi;//如果之前已经是同集合 这为环上两点 标记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(i1;in;i)if(bj[i]1)printf(%lld ,i);printf(\n);}return 0;}
