POJ 2117 Electricity.cpp

#include <cstdio>
#include <vector>
#include <set>
#include <algorithm>
using namespace std;

vector<int> edge[10005];
int dfs_clock, dfn[10005], low[10005];
int cut[10005]; //cut[i]=j表示割點i能把圖切成j個分支

void Initial(int N);
void dfs(int cur, int parent);

int main()
{
    int P, C;
    while (scanf("%d %d", &P, &C) && (P || C)) {
        if (C == 0) {
            printf("%d\n", P-1);
            continue;
        }

        Initial(P);

        for (int i = 0, x, y; i < C; ++i) {
            scanf("%d %d", &x, &y);
            edge[x].push_back(y);
            edge[y].push_back(x);
        }

        int graph_cnt = 0;
        for (int i = 0; i < P; ++i) {
            if (!dfn[i]) {
                ++graph_cnt;
                dfs(i, -1);
            }
        }
        int Max  = 0;
        for (int i = 0; i < P; ++i)
            Max = max(Max, cut[i]);

        printf("%d\n", graph_cnt + Max - 1);
    }
}
void Initial(int N)
{
    for (int i = 0; i <= N; ++i) {
        edge[i].clear();
        dfn[i] = low[i] = 0;
        cut[i] = 1;
    }
    dfs_clock = 0;
}
void dfs(int cur, int parent)
{
    int child = 0;
    bool flag = false;

    dfn[cur] = low[cur] = ++dfs_clock;

    for (int i = 0; i < edge[cur].size(); ++i) {
        int nxt = edge[cur][i];
        if (!dfn[nxt]) {
            ++child;
            dfs(nxt, cur);
            low[cur] = min(low[cur], low[nxt]);

            if (low[nxt] >= dfn[cur])
                flag = true;

            if ((parent == -1 && child > 1) || (parent != -1 && low[nxt] >= dfn[cur]))
                ++cut[cur];
        }
        else if (nxt != parent)
            low[cur] = min(low[cur], dfn[nxt]);
    }
}