【POJ1144】Network

题面太长而且是英文不贴

大意：求割点

裸题

/*To The End Of The Galaxy*/
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include<set>
#include
#include
#define debug(x) cerr<<#x<<"="<#define INF 0x7f7f7f7f
#define llINF 0x7fffffffffffll
using namespace std;
typedef pair<int,int> pii;
typedef long long ll;
inline int init()
{
    int now=0,ju=1;char c;bool flag=false;
    while(1)
    {
        c=getchar();
        if(c=='-')ju=-1;
        else if(c>='0'&&c<='9')
        {
            now=now*10+c-'0';
            flag=true;
        }
        else if(flag)return now*ju;
    }
}
inline long long llinit()
{
    long long now=0,ju=1;char c;bool flag=false;
    while(1)
    {
        c=getchar();
        if(c=='-')ju=-1;
        else if(c>='0'&&c<='9')
        {
            now=now*10+c-'0';
            flag=true;
        }
        else if(flag)return now*ju;
    }
}
int cnt,n;
struct edge
{
    int from,to,val,pre;
}Edge[100005];
int dfn[105],dfs_time,low[105],head[105];
bool iscut[105],vis[105];
inline void addedge(int from,int to,int val)
{
    ++cnt;
    Edge[cnt]=((edge){from,to,val,head[from]});
    head[from]=cnt;
}
inline void tarjan(int now,int fa)
{
    int ch=0;
    dfn[now]=low[now]=++dfs_time;
    vis[now]=1;
    for(int j=head[now];j;j=Edge[j].pre)
    {
        if(!dfn[Edge[j].to])
        {
            ch++;
            tarjan(Edge[j].to,now);
            low[now]=min(low[now],low[Edge[j].to]);
            if(low[Edge[j].to]>=dfn[now])
            {
                iscut[now]=1;
            }
        }
        else if(dfn[Edge[j].to]fa)
        {
            low[now]=min(low[now],dfn[Edge[j].to]);
        }
    }
    if(!fa)
    {
        if(ch==1)iscut[now]=0;
    }
}
int main()
{
    int n,u,v,ans;
    while(scanf("%d",&n),n)
    {
        cnt=0;memset(head,0,sizeof(head));
        ans=0;
        memset(dfn,0,sizeof(dfn));memset(low,0,sizeof(low));
        dfs_time=0;
        for(int i=1;i<=n;i++)
        {
            iscut[i]=false;
            vis[i]=false;
        }
        while(scanf("%d",&u),u)
        {
            while(getchar()!='\n')
            {
                scanf("%d",&v);
                addedge(u,v,1);
                addedge(v,u,1);
            }
        }
        for(int i=1;i<=n;i++)
        {
            if(!vis[i])
            {
                tarjan(i,0);
            }
        }
        for(int i=1;i<=n;i++)
        {
            if(iscut[i])
            {
                ans++;
            }
        }
        printf("%d\n",ans);
    }
    return 0;
}

UPD
看起来用vis是对的而且不用vis也是对的

/*To The End Of The Galaxy*/
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include<set>
#include
#include
#define debug(x) cerr<<#x<<"="<#define INF 0x7f7f7f7f
#define llINF 0x7fffffffffffll
using namespace std;
typedef pair<int,int> pii;
typedef long long ll;
inline int init()
{
    int now=0,ju=1;char c;bool flag=false;
    while(1)
    {
        c=getchar();
        if(c=='-')ju=-1;
        else if(c>='0'&&c<='9')
        {
            now=now*10+c-'0';
            flag=true;
        }
        else if(flag)return now*ju;
    }
}
inline long long llinit()
{
    long long now=0,ju=1;char c;bool flag=false;
    while(1)
    {
        c=getchar();
        if(c=='-')ju=-1;
        else if(c>='0'&&c<='9')
        {
            now=now*10+c-'0';
            flag=true;
        }
        else if(flag)return now*ju;
    }
}
int cnt,n;
struct edge
{
    int from,to,val,pre;
}Edge[100005];
int dfn[105],dfs_time,low[105],head[105];
bool iscut[105],vis[105];
inline void addedge(int from,int to,int val)
{
    ++cnt;
    Edge[cnt]=((edge){from,to,val,head[from]});
    head[from]=cnt;
}
inline void tarjan(int now,int fa)
{
    int ch=0;
    dfn[now]=low[now]=++dfs_time;
    vis[now]=1;
    for(int j=head[now];j;j=Edge[j].pre)
    {
        if(!dfn[Edge[j].to])
        {
            ch++;
            tarjan(Edge[j].to,now);
            low[now]=min(low[now],low[Edge[j].to]);
            if(low[Edge[j].to]>=dfn[now])
            {
                iscut[now]=1;
            }
        }
        else if(vis[Edge[j].to]&&Edge[j].to!=fa)
        {
            low[now]=min(low[now],dfn[Edge[j].to]);
        }
    }
    if(!fa)
    {
        if(ch==1)iscut[now]=0;
    }
}
int main()
{
    int n,u,v,ans;
    while(scanf("%d",&n),n)
    {
        cnt=0;memset(head,0,sizeof(head));
        ans=0;
        memset(dfn,0,sizeof(dfn));memset(low,0,sizeof(low));
        dfs_time=0;
        for(int i=1;i<=n;i++)
        {
            iscut[i]=false;
            vis[i]=false;
        }
        while(scanf("%d",&u),u)
        {
            while(getchar()!='\n')
            {
                scanf("%d",&v);
                addedge(u,v,1);
                addedge(v,u,1);
            }
        }
        for(int i=1;i<=n;i++)
        {
            if(!vis[i])
            {
                tarjan(i,0);
            }
        }
        for(int i=1;i<=n;i++)
        {
            if(iscut[i])
            {
                ans++;
            }
        }
        printf("%d\n",ans);
    }
    return 0;
}

UPD2

当一张图只有两个点时 根一定会被误判为割点 判掉就好

图论-tarjan双联通分量

相关

标签