UVA 315 ：Network （无向图求割顶）

题目链接

题意：求所给无向图中一共有多少个割顶

用的lrj训练指南P314的模板

#include<bits/stdc++.h>

using namespace std;

typedef long long LL;

const int N=;

struct Edge

{

    int to,next;

    Edge(){}

    Edge(int _to,int _next)

    {

        to=_to;

        next=_next;

    }

}edge[N*N*];

int head[N];

int dfn[N],low[N];

int iscut[N];

int n,tot;

int time_tag;

void addedge(int u,int v)

{

    edge[tot]=Edge(v,head[u]);

    head[u]=tot++;

}

void init()

{

    memset(dfn,,sizeof(dfn));

    memset(iscut,,sizeof(iscut));

    memset(head,-,sizeof(head));

    tot=time_tag=;

}

void dfs(int u,int pre)

{

    low[u]=dfn[u]=++time_tag;

    int child=;    //子节点数目

    for(int i=head[u];~i;i=edge[i].next)

    {

        int v=edge[i].to;

        if(!dfn[v])    //    把dfn[]当vis[]使用

        {

            child++;

            dfs(v,u);

            low[u]=min(low[u],low[v]);

            if(low[v]>=dfn[u])

                iscut[u]=;

        }

        else if(dfn[v]<dfn[u] && v!=pre)

            low[u]=min(low[u],dfn[v]);

    }

    if(pre<&&child==) iscut[u]=;    //只有一个孩子的根节点

}

int main()

{

    while(scanf("%d",&n)>&&n)

    {

        init();

        int u,v;

        while(scanf("%d",&u)>&&u)

        {

            while(getchar()!='\n')

            {

                scanf("%d",&v);

                addedge(u,v);

                addedge(v,u);

            }

        }

        dfs(,-);

        int ans=;

        for(int i=;i<=n;i++)

            if(iscut[i]) ans++;

        printf("%d\n",ans);

    }

}