poj1144 Network【tarjan求割点】

转载请注明出处，谢谢：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=,int _next=){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,);

    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]=;

    int tot=;

    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== && tot>)   //根结点有两个或两个以上子节点时才是割点

                cut[u]=;

            else if(u!= && low[v]>=dfn[u])   //非根结点为割点当且仅当存在一个子节点v，使v以及v的后代都没有返回u的祖先的反向边

                cut[u]=;

        }

        else if(inst[v] && dfn[v]<low[u])

            low[u]=dfn[v];

    }

}

int main()

{_

    int n;

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

    {

        CLR(head,);CLR(dfn,);

        CLR(inst,);CLR(cut,);

        cnt=;

        int u;

        int ec=;

        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(,-);

        int ans=;

        REP(i,n)

            if(cut[i])

                ans++;

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

    }

    return ;

}

秒客网

poj1144 Network【tarjan求割点】

相关文章