题目链接：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;}

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