Educational Codeforces Round 42 (Rated for Div. 2) F. Simple Cycles Edges（点双联通分量）

本文主要是介绍Educational Codeforces Round 42 (Rated for Div. 2) F. Simple Cycles Edges（点双联通分量），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目链接：http://codeforces.com/contest/962/problem/F

点双，把每个边属于拿个联通分量搞出来，然后判断每个联通分量里的点和边的数目是否相等，如果相等则所有边都属于一个简单环，直接上Tarjan点双的板子就行了，主义割点可以属于多个联通分量

代码：

#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e5+5;//点数
const int MAXM=2e5+5;//边数，因为是无向图，所以这个值要*2
struct node
{int next,to,id;
}edge[MAXM];bool Instack[MAXN],cut[MAXN],vis[MAXM];
int head[MAXN],DFN[MAXN],Low[MAXN],Belong[MAXM],Stack[MAXM];
int tot,Index,root,top,block;void addedge(int u,int v,int id)
{edge[tot].to=v;edge[tot].id=id;edge[tot].next=head[u];head[u]=tot++;
}void Tarjan(int u,int fa)//fa初值一定要为-1
{int cnt=0;DFN[u]=Low[u]=++Index;Instack[u]=1;for(int i=head[u];~i;i=edge[i].next){int v=edge[i].to;if(vis[edge[i].id]) continue;vis[edge[i].id]=true;Stack[++top]=edge[i].id;if(DFN[v]==-1){Tarjan(v,u);cnt++;if(Low[u]>Low[v]) Low[u]=Low[v];if(fa<0&&cnt>1) cut[u]=1;else if(fa>=0&&Low[v]>=DFN[u]) cut[u]=1;if(Low[v]>=DFN[u]){int t;block++;do{t=Stack[top--];Belong[t]=block;}while(t!=edge[i].id);}}else if(Instack[v]&&Low[u]>DFN[v])Low[u]=DFN[v];}
}void init()
{memset(DFN,-1,sizeof(DFN));memset(Low,0,sizeof(Low));memset(Instack,0,sizeof(Instack));memset(cut,0,sizeof(cut));memset(head,-1,sizeof(head));memset(vis,false,sizeof(vis));tot=0;Index=0;top=0;block=0;
}
bool ans[MAXM],bk[MAXM],ou[MAXM];
int cntp[MAXM],cnte[MAXM];
void solve(int n,int m)
{for(int i=1;i<=n;i++)if(DFN[i]==-1)Tarjan(i,-1);memset(cntp,0,sizeof(cntp));memset(cnte,0,sizeof(cnte));memset(bk,false,sizeof(bk));for(int i=1;i<=n;i++){for(int j=head[i];~j;j=edge[j].next){int id=edge[j].id;id=Belong[id];cnte[id]++;if(!bk[id]){bk[id]=true;cntp[id]++;}}for(int j=head[i];~j;j=edge[j].next){int id=edge[j].id;id=Belong[id];bk[id]=false;}}for(int i=1;i<=block;i++){cnte[i]/=2;if(cnte[i]==cntp[i]) ans[i]=true;}for(int i=1;i<=n;i++)for(int j=head[i];~j;j=edge[j].next){int id=edge[j].id;id=Belong[id];if(ans[id])ou[edge[j].id]=true;}int tot=0;for(int i=1;i<=m;i++){if(ou[i]) tot++;}printf("%d\n",tot);for(int i=1;i<=m;i++){if(ou[i]) printf("%d ",i);}puts("");
}
int main()
{//freopen("in.txt","r",stdin);int n,m;int u,v;while(~scanf("%d%d",&n,&m)){init();for(int i=1;i<=m;i++){scanf("%d%d",&u,&v);addedge(u,v,i);addedge(v,u,i);}solve(n,m);}return 0;
}

这篇关于Educational Codeforces Round 42 (Rated for Div. 2) F. Simple Cycles Edges（点双联通分量）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---