hihoCoder1183tarjan算法应用之割边和割点

xiaoxiao2021-02-28  142

#include<cstdio> #include<vector> #include<algorithm> using namespace std; int n,m,order=0; int low[20004],dfn[20004],father[20004],son[20004]; //father:父结点 son:子结点个数 vector<int> cutpoint,edge[20004]; vector< pair<int,int> > cutedge; void tarjan(int u) { dfn[u]=low[u]=++order; bool flag=false; for (int i=0;i<edge[u].size();i++) { int v=edge[u][i]; if(!dfn[v]) { son[u]++; father[v]=u; tarjan(v); if(low[v]>=dfn[u]) flag=true; //点u为割点 if(low[v]>dfn[u]) cutedge.push_back(make_pair(min(v,u),max(v,u))); //边v-u为割边 low[u]=min(low[u],low[v]); } else if(v!=father[u]) low[u]=min(low[u],dfn[v]); } //根节点若有两棵或两棵以上的子树则该为割点 //非根节点若所有子树节点均没有指向u的祖先节点的回边则为割点 if((father[u]==0&&son[u]>1)||(father[u]&&flag)) cutpoint.push_back(u); } int main() { scanf("%d%d",&n,&m); for (int i=1;i<=m;i++) { int u,v; scanf("%d%d",&u,&v); edge[u].push_back(v),edge[v].push_back(u); } tarjan(1); sort(cutedge.begin(),cutedge.end()); sort(cutpoint.begin(),cutpoint.end()); if(0==cutpoint.size()) puts("Null"); else { printf("%d",cutpoint[0]); for (int i=1;i<cutpoint.size();i++) printf(" %d",cutpoint[i]); puts(""); } for(int i=0;i<cutedge.size();i++) printf("%d %d\n",cutedge[i].first,cutedge[i].second); }
转载请注明原文地址: https://www.6miu.com/read-22512.html

最新回复(0)