Programming學習筆記: POJ 2117 Electricity

題意：
這題是將graph中移除一個點，graph會變成D個獨立部分，求D的最大値。
第一行輸入P和C表示有P個點(0~P-1)和C條邊，每條邊都是雙向的。

想法：
分成兩個

如果C==0表示P個點沒有任何的邊，直接輸出P-1
本來的圖就分成N部分(N可能==1表示所有點都是連通的，但N也可能>1)，移除某個點i能將該部分再分成cut[i]部分，那麼其中一個候選答案為N+cut[i]-1，找到最大的候選答案。套Cut Vertex模板求cut[i]。

第二點舉個例子：

5 3

0 1

1 2

3 4

表示0,1,2和3,4不連通，所以N==2，N是固定的，然後例如移除點1，cut[1]==2(因為(0,1,2)這部分移除點1會將0,2分開變成2個部分)，因此候選答案就是2+2-1=3，也是這個測資的解答。

	#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]);
	}
	}

Programming學習筆記