首页 > 代码库 > 未完成存档
未完成存档
//http://poj.org/problem?id=2117#include <cstring>#include <ctype.h>#include <cstdio>#include <cmath>#define N 10005void read(int &x){ x=0; char ch=getchar(); for(;!isdigit(ch);ch=getchar()); for(;isdigit(ch);ch=getchar()) x=x*10+ch-‘0‘;}struct Edge{ int next,to; Edge (int next=0,int to=0) :next(next),to(to) {}}edge[N<<1];bool vis[N],cutpoint[N];int head[N],cnt=-1,n,m,dfn[N],low[N],tim;void init(){ memset(head,0,sizeof(head)); cnt=-1; tim=0; memset(dfn,0,sizeof(dfn)); memset(vis,0,sizeof(vis)); memset(low,0,sizeof(low)); }void insert(int u,int v){ edge[++cnt]=Edge(head[u],v); head[u]=cnt;}int min(int a,int b) {return a>b?b:a;}void tarjan(int x,int pre){ vis[x]=1; low[x]=dfn[x]=++tim; int sum=0; bool flag=false; for(int u=head[x];u!=-1;u=edge[u].next) { if((u^1)!=pre) { if(!vis[edge[u].to]) { sum++; tarjan(edge[u].to); low[x]=min(low[x],low[edge[u].to]); if(low[edge[u].to]>=dfn[x]) flag=true; } else low[x]=min(low[x],dfn[edge[u].to]); } } if(pre==-1) if(sum>1) cutpoint[x]=true; else if(flag) cutpoint[x]=true;}int main(){ while(scanf("%d%d",&n,&m)!=EOF) { init(); for(int x,y;m--;) { read(x); read(y); insert(x,y); insert(y,x); } for(int i=1;i<=n;i++) if(!vis[i]) tarjan(i,-1); }}
未完成存档
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。