# 題目: UVa 10765 - Doves and Bombs

# 題目說明

給一個無向圖，當拿掉一個割點時，此圖會分成數個連通圖
求前m個可以分為最多連通圖的點及連通圖的數量

---

INPUT:
每筆測資第一行有兩個整數n、m，當n、m為0時結束

1. n代表節點數
2. m代表輸出m筆結果(降冪排序)
   接下來每行有兩個整數，代表兩整數存在一條邊連通
   當兩整數為-1時結束

---

OUTPUT:
輸出前m筆結果(降冪排序)

# 解題方法

先建圖，建雙向邊
之後跑dfs，紀錄每個點的dfn值及low值
以割點的定義紀錄每個點被多少個點視為割點
最後排序後輸出

# 參考程式碼

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

vector< vector<int> > graph;
vector<int> dfn, low;
vector< pair<int, int> > result;
int dep;

void dfs(int cur, int par)
{
	int child = 0;
	dfn[cur] = low[cur] = ++dep;

	for (auto& i : graph[cur]) {

		if (!dfn[i]) {
			++child;
			dfs(i, cur);
			low[cur] = min(low[cur], low[i]);
		}
		else {
			if (i != par) low[cur] = min(low[cur], dfn[i]);
			continue;
		}

		if (low[i] >= dfn[cur] && (par != -1 || child >= 2)) ++result[cur].second;
	}
}

int cmp(pair<int, int>& a, pair<int, int>& b)
{
	return a.second == b.second ? a.first < b.first : a.second > b.second;
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);

	int n, m;
	while (cin >> n >> m, n && m) {

		// init
		graph.assign(n, vector<int>());
		dfn.assign(n, 0);
		low.assign(n, 0);
		result.clear();
		for (int i = 0; i < n; ++i) result.push_back(pair<int, int>(i, 1));
		dep = 0;

		// build graph
		int a, b;
		while (cin >> a >> b, a != -1 && b != -1) {
			graph[a].emplace_back(b);
			graph[b].emplace_back(a);
		}

		// find articulation point
		for (int i = 0; i < n; ++i) if (!dfn[i]) dfs(i, -1);

		// sort
		sort(result.begin(), result.end(), cmp);

		for (int i = 0; i < m; ++i) cout << result[i].first << " " << result[i].second << "\n";
		cout << "\n";
	}

	return 0;
}

# 參考資料

https://www.larrysprognotes.com/UVa%20-%2010765/