poj1144 Network【tarjan求割点】

浏览数：61 / 时间：2015年06月09日

转载请注明出处，谢谢：http://www.cnblogs.com/KirisameMarisa/p/4319585.html ---by 墨染之樱花

【题目描述】（半天才看明白。。。）给图求割点个数

【思路】直接套求割点的模板即可，就是要注意输入比较坑。代码见下，附注释

#include <iostream>
#include <ios>
#include <iomanip>
#include <functional>
#include <algorithm>
#include <vector>
#include <sstream>
#include <list>
#include <queue>
#include <deque>
#include <stack>
#include <string>
#include <set>
#include <map>
#include <cstdio>
#include <cstdlib>
#include <cctype>
#include <cmath>
#include <cstring>
#include <climits>
using namespace std;
#define XINF INT_MAX
#define INF 1<<30
#define MAXN 110
#define eps 1e-10
#define zero(a) fabs(a)<eps
#define sqr(a) ((a)*(a))
#define MP(X,Y) make_pair(X,Y)
#define PB(X) push_back(X)
#define PF(X) push_front(X)
#define REP(X,N) for(int X=0;X<N;X++)
#define REP2(X,L,R) for(int X=L;X<=R;X++)
#define DEP(X,R,L) for(int X=R;X>=L;X--)
#define CLR(A,X) memset(A,X,sizeof(A))
#define IT iterator
#define PI  acos(-1.0)
#define test puts("OK");
#define _ ios_base::sync_with_stdio(0);cin.tie(0);
typedef long long ll;
typedef pair<int,int> PII;
typedef priority_queue<int,vector<int>,greater<int> > PQI;
typedef vector<PII> VII;
typedef vector<int> VI;
#define X first
#define Y second

struct edge
{
    int to,next;
    edge(int _to=0,int _next=0){to=_to;next=_next;}
} edges[MAXN*MAXN];

int head[MAXN];
int low[MAXN];   //非父边指向的最早访问的祖先 
int dfn[MAXN];   //时间戳 
int cnt;     //记录时间 
bool inst[MAXN]; 
bool cut[MAXN];   //判断是否是割点 

inline void addedge(int x,int y,int &eCnt)
{
    edge e(y,0);
    edges[eCnt]=e;
    edges[eCnt].next=head[x];
    head[x]=eCnt;
    eCnt++;
}

void tarjan(int u,int fa)
{
    low[u]=dfn[u]=++cnt;
    inst[u]=1;
    int tot=0;
    for(int i=head[u];i;i=edges[i].next)
    {
        int v=edges[i].to;
        if(v==fa)
            continue;
        if(!dfn[v])
        {
            tarjan(v,u);
            tot++;
            if(low[v]<low[u])
                low[u]=low[v];
            if(u==0 && tot>1)   //根结点有两个或两个以上子节点时才是割点 
                cut[u]=1;
            else if(u!=0 && low[v]>=dfn[u])   //非根结点为割点当且仅当存在一个子节点v，使v以及v的后代都没有返回u的祖先的反向边 
                cut[u]=1;
        }
        else if(inst[v] && dfn[v]<low[u])
            low[u]=dfn[v];
    }
}

int main()
{_
    int n;
    while(~scanf("%d",&n) && n)
    {
        CLR(head,0);CLR(dfn,0);
        CLR(inst,0);CLR(cut,0);
        cnt=0;
        int u;
        int ec=1;
        while(scanf("%d",&u) && u)
        {
            u--;
            char c;
            int v;
            while(scanf("%c",&c) && c!=‘\n‘)
            {
                scanf("%d",&v);
                v--;
                addedge(u,v,ec);
                addedge(v,u,ec);
            }
        }
        tarjan(0,-1);
        int ans=0;
        REP(i,n)
            if(cut[i])
                ans++;
        printf("%d\n",ans);
    }
    return 0;
}