UVa 315 & POJ 1144 Network

題意：
    critical point指的是在一個connected graph中，如果移除該點，會使得該graph不再connected，則該點為critical point(cut vertex，割點)，現在給你一個graph，求critical point的數量。
    給你一個N表示共有N個點，底下最多N行，以0表示本次case輸入完畢，每行有a,b1,b2,b3.....，表示(a,b1),(a,b2),(a,b3)為邊，記得建邊的時候為雙向。

想法：
     cut vertex模板題 。

	#include <cstdio>
	#include <iostream>
	#include <sstream>
	#include <vector>
	#include <algorithm>
	using namespace std;
	vector<int> edge[105];
	int dfs_clock, dfn[105], low[105];
	int ans;
	void dfs(int cur, int parent)
	{
	int child = 0;
	bool flag = false;
	low[cur] = dfn[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;
	}
	else if (nxt != parent)
	low[cur] = min(low[cur], dfn[nxt]);
	}
	if ((child >= 2 || parent != -1) && flag)
	++ans;
	}
	int main()
	{
	int N;
	string line;
	while (scanf("%d ", &N) && N) {
	// Intital
	dfs_clock = 0;
	ans = 0;
	for (int i = 0; i <= N; ++i) {
	edge[i].clear();
	dfn[i] = 0, low[i] = 0;
	}
	// Input
	int a, b;
	while (getline(cin, line)) {
	stringstream ss(line);
	ss >> a;
	if (!a) break;
	while (ss >> b) {
	edge[a].push_back(b);
	edge[b].push_back(a);
	}
	}
	dfs(1, -1);
	printf("%d\n", ans);
	}
	}

view raw [POJ] 1144 Network.cpp hosted with ❤ by GitHub