[TIOJ] 2050. 尋找關節點 EXTREME

題目連結:https://tioj.infor.org/problems/2050

---

上次來這裡寫東西好像是超級久以前ㄌXD
貼一下昨天吃飯聽到的做法，但是我不會證明，求知道的人貼個 paper 給我 (｡･∀･)ﾉﾞ，只知道這是蔡孟宗教授在我高二那年二階講的算法。
這題重點是如何把一張圖的邊減少到 $O(N)$ 量級，但還是保持著一些必要的連通性。如果我昨天吃飯的時候沒聽錯的話，我們可以做 $k$ 次 BFS 來找出生成森林，每次找出來後就把它從原圖中拔掉，並記錄到我們最後要取的邊集中，如果要求雙連通分量的話，那 $k=2$ ，而像這題是某種三連通，所以 $k=3$。
所以這題就把邊減少到 $O(N)$ 量集後就可以拔掉每個點，跑一次 tarjan 找出所有其他割點，不過有一些小細節要注意一下，例如拔掉一條鍊的最邊邊兩個點不會讓圖變得不連通之類ㄉ。

#include <bits/stdc++.h>
using namespace std;
const int N = 2000 + 5;
const int M = 2000000 + 5;

class BCC_AP {
	private:
		int n, ecnt;
		vector<vector<pair<int,int>>> G;
		vector<int> bcc, dfn, low, st;
		vector<bool> ap, ins;
		void dfs(int u, int f) {
			dfn[u] = low[u] = dfn[f] + 1;
			int ch = 0;
			for (auto [v, t]: G[u]) if (v != f) {
				if (not ins[t]) {
					st.push_back(t);
					ins[t] = true;
				}
				if (dfn[v]) {
					low[u] = min(low[u], dfn[v]);
					continue;
				} ++ch; dfs(v, u);
				low[u] = min(low[u], low[v]);
				if (low[v] >= dfn[u]) {
					ap[u] = true;
					while (true) {
						int eid = st.back(); st.pop_back();
						bcc[eid] = ecnt;
						if (eid == t) break;
					}
					ecnt++;
				}
			}
			if (ch == 1 and u == f) ap[u] = false;
		}
	public:
		void init(int n_) {
			G.clear(); G.resize(n = n_);
			ecnt = 0; ap.assign(n, false);
			low.assign(n, 0); dfn.assign(n, 0);
		}
		void add_edge(int u, int v) {
			G[u].emplace_back(v, ecnt);
			G[v].emplace_back(u, ecnt++);
		}
		void solve() {
			ins.assign(ecnt, false);
			bcc.resize(ecnt); ecnt = 0;
			for (int i = 0; i < n; ++i)
				if (not dfn[i]) dfs(i, i);
		}
		int get_id(int x) { return bcc[x]; }
		int count() { return ecnt; }
		bool is_ap(int x) { return ap[x]; }
} bcc_ap, bcc2;

bool chosen[M];
vector<pair<int,int>> G[N];
int vis[N], deg[N];

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	int n, m; cin >> n >> m;
	for (int i = 0; i < m; ++i) {
		int u, v; cin >> u >> v;
		G[--u].emplace_back(--v, i);
		G[v].emplace_back(u, i);
		deg[u]++, deg[v]++;
	}
	vector<pair<int,int>> reduced;
	auto bfs = [&reduced](int s, int ts){
		vis[s] = ts;
		queue<int> q; q.push(s);
		while (not q.empty()) {
			int u = q.front(); q.pop();
			for (auto [v, t]: G[u]) {
				if (chosen[t]) continue;
				if (vis[v] == ts) continue;
				vis[v] = ts; chosen[t] = true;
				q.push(v); reduced.emplace_back(u, v);
			}
		}
	};
	for (int iter = 1; iter <= 3; ++iter) {
		for (int u = 0; u < n; ++u) {
			if (vis[u] == iter) continue;
			bfs(u, iter);
		}
	}
	bcc_ap.init(n);
	for (auto [u, v]: reduced) {
		bcc_ap.add_edge(u, v);
	}
	bcc_ap.solve();

	auto mark = [](int s, int b, int ts) {
		vis[s] = ts;
		queue<int> q; q.push(s);
		while (not q.empty()) {
			int u = q.front(); q.pop();
			for (auto [v, t]: G[u]) {
				if (vis[v] == ts) continue;
				if (v == b) continue;
				vis[v] = ts; q.push(v); 
			}
		}
	};

	int ans = 0, iter = 3;
	for (int u = 0; u < n; ++u) {
		if (bcc_ap.is_ap(u)) {
			int cnt = 0; ++iter;
			for (int v = 0; v < n; ++v) {
				if (vis[v] == iter) continue;
				if (u == v) continue;
				cnt++; mark(v, u, iter);
			}
			ans += n - 1 - u;
			if (cnt == 2) {
				for (auto [v, t] : G[u])
					if (deg[v] == 1 and v > u)
						--ans;
			}
			continue;
		}
		bcc2.init(n);
		for (auto [a, b]: reduced) {
			if (a != u and b != u) {
				bcc2.add_edge(a, b);
			}
		}
		bcc2.solve();
		for (int v = u + 1; v < n; ++v)
			if (bcc2.is_ap(v)) ans++;
	}
	cout << ans << '\n';
	return 0;
}