首页 > 代码库 > 未完成存档

未完成存档

//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);    }}

 

未完成存档