POJ3177 Redundant Paths 边双联通分支

2019-04-14 16:44发布

站内文章 / 模拟电子
13531 0 1503
最近在刷连通图，这道题是上海大学kuangbin模板上的题。 先附上一个总结博客Orz：https://blog.csdn.net/qq_39599067/article/details/81321884 kuangbin模板上的方法，是按桥边建树。（可能不需要考虑重边？？）附上AC代码： #include #include #include #include #include #include #include #include using namespace std; typedef pair pp; const int MAXN=5010; const int MAXM=10010*2;//因为是无向图,所以边数×2 struct Edge { int to,next; bool iscut;//是否为桥 }edge[MAXM]; int head[MAXN],tot; int low[MAXN],dfn[MAXN],st[MAXN]; int be[MAXN]; int inde,top; int block;//边双联通块数 bool inst[MAXN]; int bridge; void init() { tot=0; memset(head,-1,sizeof(head)); } void addedge(int u,int v) { edge[tot].to=v;edge[tot].next=head[u];edge[tot].iscut=false; head[u]=tot++; } void Tarjan(int u,int pre) { int v; low[u]=dfn[u]=++inde; st[top++]=u; inst[u]=true; for(int i=head[u];i!=-1;i=edge[i].next) { v=edge[i].to; if(v==pre)//注意!! continue; if(!dfn[v]) { Tarjan(v,u); if(low[u]>low[v]) low[u]=low[v]; //桥 if(low[v]>dfn[u]) { bridge++; edge[i].iscut=true; edge[i^1].iscut=true; } } else if(inst[v]&&low[u]>dfn[v]) low[u]=dfn[v]; } if(low[u]==dfn[u]) { block++; do { v=st[--top]; inst[v]=false; be[v]=block; }while(v!=u); } } void solve(int n) { memset(dfn,0,sizeof(dfn)); memset(inst,false,sizeof(inst)); inde=top=0; bridge=0;block=0; Tarjan(1,0); int ans=0; int deg[MAXN]; memset(deg,0,sizeof(deg)); for(int i=1;i<=n;i++) for(int j=head[i];j!=-1;j=edge[j].next) { if(edge[j].iscut) deg[be[i]]++; } for(int i=1;i<=block;i++)//注意是block if(deg[i]==1) ans++; //cout<<"ans="< Tarjan算法的原理，，我一直都看不懂55555... 后来在想，建树的过程能不能用“不属于同一个联通子图”来建呢？就是把if(edge[j].iscut)改成if(be[i]!=be[edge[j].to])。试着交了一发，WA了。。后来看了大佬博客Orz： https://blog.csdn.net/GYH0730/article/details/81053482 https://blog.csdn.net/hpuhjh/article/details/47752065 发现可能有没有注意到重边问题。。再一改，过了。。果然我对原理的理解还是太差了QAQ。。。 附上AC代码： #include #include #include #include #include #include #include #include using namespace std; typedef pair pp; const int MAXN=5010; const int MAXM=10010*2;//因为是无向图,所以边数×2 struct Edge { int to,next; bool iscut;//是否为桥 }edge[MAXM]; int head[MAXN],tot; int low[MAXN],dfn[MAXN],st[MAXN]; int be[MAXN]; int inde,top; int block;//边双联通块数 bool inst[MAXN]; int bridge; void init() { tot=0; memset(head,-1,sizeof(head)); } void addedge(int u,int v) { edge[tot].to=v;edge[tot].next=head[u];edge[tot].iscut=false; head[u]=tot++; } void Tarjan(int u,int pre) { int v; low[u]=dfn[u]=++inde; st[top++]=u; inst[u]=true; int sign=0; for(int i=head[u];i!=-1;i=edge[i].next) { v=edge[i].to; if(v==pre&&sign==0)//注意!!处理重边 { sign++; continue; } if(!dfn[v]) { Tarjan(v,u); if(low[u]>low[v]) low[u]=low[v]; //桥 if(low[v]>dfn[u]) { bridge++; edge[i].iscut=true; edge[i^1].iscut=true; } } else if(inst[v]&&low[u]>dfn[v]) low[u]=dfn[v]; } if(low[u]==dfn[u]) { block++; do { v=st[--top]; inst[v]=false; be[v]=block; }while(v!=u); } } void solve(int n) { memset(dfn,0,sizeof(dfn)); memset(inst,false,sizeof(inst)); inde=top=0; bridge=0;block=0; Tarjan(1,0); int ans=0; int deg[MAXN]; memset(deg,0,sizeof(deg)); for(int i=1;i<=n;i++) for(int j=head[i];j!=-1;j=edge[j].next) { int u=be[i],v=be[edge[j].to];//注意是edge[j].to! if(u!=v)//第二种建树方法 deg[u]++,deg[v]++; } for(int i=1;i<=block;i++) if(deg[i]==2) ans++; //cout<<"ans="<  

热门文章