poj 2117 Electricity（tarjan求割点删掉之后的连通块数）

题目链接：http://poj.org/problem?id=2117

题意：求删除一个点后，图中最多有多少个连通块。

题解：就是找一下割点，根节点的割点删掉后增加son-1（son为子树个数），非根节点删掉之后++

#include <iostream>

#include <cstring>

#include <cstdio>

using namespace std;

const int N = 1e4 + 10;

const int M = 1e6 + 10;

struct TnT {

    int v , next;

    bool cut;

}edge[M];

int head[N] , e;

int Low[N] , DFN[N] , Stack[N] , add_block[N];

bool Instack[N];

bool cut[N];

int Index , bridge , top;

void init() {

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

    e = 0;

}

void add(int u , int v) {

    edge[e].v = v , edge[e].next = head[u] ,edge[e].cut = false , head[u] = e++;

}

void Tarjan(int u , int pre) {

    int v;

    Low[u] = DFN[u] = ++Index;

    Stack[top++] = u;

    Instack[u] = true;

    int son = 0;

    for(int i = head[u] ; i != -1 ; i = edge[i].next) {

        v = edge[i].v;

        if(v == pre) continue;

        if(!DFN[v]) {

            son++;

            Tarjan(v , u);

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

            if(Low[v] > DFN[u]) {

                bridge++;

                edge[i].cut = true;

                edge[i^1].cut = true;

            }

            if(u != pre && Low[v] >= DFN[u]) {

                cut[u] = true;

                add_block[u]++;

            }

        }

        else if(Instack[v]) Low[u] = min(Low[u] , DFN[v]);

    }

    if(u == pre && son > 1) cut[u] = true;

    if(u == pre) add_block[u] = son - 1;

    Instack[u] = false;

    top--;

}

int main() {

    int p , c;

    while(~scanf("%d%d" , &p , &c)) {

        if(p == 0 && c == 0) break;

        init();

        for(int i = 0 ; i < c ; i++) {

            int u , v;

            scanf("%d%d" , &u , &v);

            add(u , v);

            add(v , u);

        }

        memset(DFN , 0 , sizeof(DFN));

        memset(Instack , false , sizeof(Instack));

        memset(add_block , 0 , sizeof(add_block));

        memset(cut , false , sizeof(cut));

        int cnt = 0;

        Index = 0 , bridge = 0 , top = 0;

        for(int i = 0 ; i < p ; i++) {

            if(!DFN[i]) {

                Tarjan(i , i) , cnt++;

            }

        }

        int MAX = 0;

        for(int i = 0 ; i < p ; i++) MAX = max(MAX , cnt + add_block[i]);

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

    }

    return 0;

}