首页 > 代码库 > Road Construction(poj 3352)
Road Construction(poj 3352)
题意:求最少天几条边,使这个无向图变成双连通图。
/* tarjan缩点后,形成一棵树,求出叶子节点数tot,答案是(tot+1)/2 */ #include<cstdio> #include<cstring> #include<iostream> #define N 1010 using namespace std; int num[N],low[N],instack[N],vis[N],s[N],in[N],belong[N],top,cnt,indexx; int head[N],n,m; struct node { int v,pre; };node e[N*2]; void add(int i,int x,int y) { e[i].v=y; e[i].pre=head[x]; head[x]=i; } void tarjan(int u,int fa) { num[u]=low[u]=++indexx; vis[u]=instack[u]=1; s[++top]=u; for(int i=head[u];i!=-1;i=e[i].pre) if((fa^1)!=i) { int v=e[i].v; if(!vis[v]) { tarjan(v,i); low[u]=min(low[v],num[u]); } else if(instack[v]) low[u]=min(low[v],low[u]); } int x; if(num[u]==low[u]) { ++cnt; do { x=s[top--]; instack[x]=0; belong[x]=cnt; }while(u!=x); } } void work() { for(int i=1;i<=m;i++) { int x,y;scanf("%d%d",&x,&y); add(i*2-2,x,y);add(i*2-1,y,x); } for(int i=1;i<=n;i++) if(!vis[i])tarjan(i,-1); for(int i=1;i<=n;i++) for(int j=head[i];j!=-1;j=e[j].pre) if(belong[i]!=belong[e[j].v]) in[belong[e[j].v]]++; int tot=0; for(int i=1;i<=cnt;i++) if(in[i]==1)tot++; printf("%d\n",(tot+1)/2); } int main() { while(scanf("%d%d",&n,&m)!=EOF) { top=cnt=indexx=0; memset(num,0,sizeof(num)); memset(low,0,sizeof(low)); memset(instack,0,sizeof(instack)); memset(vis,0,sizeof(vis)); memset(s,0,sizeof(s)); memset(head,-1,sizeof(head)); memset(e,0,sizeof(e)); memset(in,0,sizeof(in)); memset(belong,0,sizeof(belong)); work(); } return 0; }
Road Construction(poj 3352)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。