POJ - 1523 SPF

题目要求割顶集，并且还要求出去掉割顶之后剩下的图连通数目。

tarjan算法求出割顶后直接枚举就可以了吧。

一开始想到利用iscut[u]的次数也就是点u被判定为割顶的次数求连通分量数，还有利用与结点u相连的点的bccno不同的编号来判定，都是不行的，具体原因自己想清楚比较好。

以后就不会犯这样的错误了。

代码：

#include <iostream>

#include <sstream>

#include <cstdio>

#include <climits>

#include <cstring>

#include <cstdlib>

#include <string>

#include <stack>

#include <map>

#include <cmath>

#include <vector>

#include <queue>

#include <algorithm>

#define esp 1e-6

#define pi acos(-1.0)

#define pb push_back

#define lson l, m, rt<<1

#define rson m+1, r, rt<<1|1

#define mp(a, b) make_pair((a), (b))

#define in  freopen("in.txt", "r", stdin);

#define out freopen("out.txt", "w", stdout);

#define print(a) printf("%d\n",(a));

#define bug puts("********))))))");

#define stop  system("pause");

#define Rep(i, c) for(__typeof(c.end()) i = c.begin(); i != c.end(); i++)

#define inf 0x0f0f0f0f

using namespace std;

typedef long long  LL;

typedef vector<int> VI;

typedef pair<int, int> pii;

typedef vector<pii,int> VII;

typedef vector<int>:: iterator IT;

const int maxn = ;

int pre[maxn], iscut[maxn], vis[maxn], low[maxn], bccno[maxn], dfs_clock, bcc_cnt;

VI g[maxn], bcc[maxn];

int flag;

struct edge

{

    int u, v;

    edge(int u, int v):u(u), v(v) {}

};

stack<edge> S;

int dfs(int u, int fa)

{

    int lowu = pre[u] = ++dfs_clock;

    int child = ;

    for(int i = ; i < g[u].size(); i++)

    {

        int v = g[u][i];

        edge e = edge(u, v);

        if(!pre[v])

        {

            S.push(e);

            child++;

            int lowv = dfs(v, u);

            lowu = min(lowu, lowv);

            if(lowv >= pre[u])

            {

                bcc_cnt++;

                bcc[bcc_cnt].clear();

                iscut[u] = ;

                for(;;)

                {

                    edge x = S.top();

                    S.pop();

                    if(bccno[x.u] != bcc_cnt)

                    {

                        bccno[x.u] = bcc_cnt;

                        bcc[bcc_cnt].pb(x.u);

                    }

                    if(bccno[x.v] != bcc_cnt)

                    {

                        bccno[x.v] = bcc_cnt;

                        bcc[bcc_cnt].pb(x.v);

                    }

                    if(x.u == u && x.v == v) break;

                }

            }

        }

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

        {

            S.push(e);

            lowu = min(lowu, pre[v]);

        }

    }

    if(child ==  && fa < )

    {

        iscut[u] = ;

    }

    return low[u] = lowu;

}

void find_bcc(int n)

{

    memset(pre, , sizeof(pre));

    memset(iscut, , sizeof(iscut));

    memset(bccno, , sizeof(bccno));

    dfs_clock = bcc_cnt = ;

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

        if(!pre[i])

            dfs(i, -);

}

void dfs1(int u)

{

    vis[u] = ;

    for(int i = ; i < g[u].size(); i++)

    {

        int v = g[u][i];

        if(!vis[v])

        {

            dfs1(v);

        }

    }

}

void init(void)

{

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

        g[i].clear();

}

int main(void)

{

    int n;

    int u, v;

    int t = ;

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

    {

        init();

        flag = ;

        n = ;

        scanf("%d", &v);

        g[u].pb(v);

        g[v].pb(u);

        n = max(max(u, v), n);

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

        {

            scanf("%d", &v);

            g[u].pb(v);

            g[v].pb(u);

            n = max(max(u, v), n);

        }

        find_bcc(n);

        if(t) puts("");

        t++;

        printf("Network #%d\n", t);

        for(int u = ; u <= ; u++)

            if(iscut[u])

            {

                flag = ;

                memset(vis, , sizeof(vis));

                int cnt = ;

                vis[u] = ;

                for(int i = ; i < g[u].size(); i++)

                {

                    int  v = g[u][i];

                    if(!vis[v])

                        cnt++, dfs1(v);

                }

                printf("  SPF node %d leaves %d subnets\n", u, cnt);

            }

        if(!flag)

        {

            puts("  No SPF nodes");

        }

    }

    return ;

}