We Need More Bosses

题面翻译

题目大意：

给定一个\(n\)个点\(m\)条边的无向图，找到两个点\(s,t\)，使得\(s\)到\(t\)必须经过的边最多（一条边无论走哪条路线都经过ta，这条边就是必须经过的边），\(2<=n<=3*10^5,1<=m<=3*10^5\)

输入格式：

第一行两个整数，\(n,m\)

以下m行，每行两个整数\(x,y\)，表示\(xy\)间有一条无向边相连

输出格式：

一个整数，即最多的必须经过边数

感谢@守望 提供翻译

题目描述

Your friend is developing a computer game. He has already decided how the game world should look like — it should consist of $ n $ locations connected by $ m $ two-way passages. The passages are designed in such a way that it should be possible to get from any location to any other location.

Of course, some passages should be guarded by the monsters (if you just can go everywhere without any difficulties, then it's not fun, right?). Some crucial passages will be guarded by really fearsome monsters, requiring the hero to prepare for battle and designing his own tactics of defeating them (commonly these kinds of monsters are called bosses). And your friend wants you to help him place these bosses.

The game will start in location $ s $ and end in location $ t $ , but these locations are not chosen yet. After choosing these locations, your friend will place a boss in each passage such that it is impossible to get from $ s $ to $ t $ without using this passage. Your friend wants to place as much bosses as possible (because more challenges means more fun, right?), so he asks you to help him determine the maximum possible number of bosses, considering that any location can be chosen as $ s $ or as $ t $ .

输入格式

The first line contains two integers $ n $ and $ m $ ( $ 2 \le n \le 3 \cdot 10^5 $ , $ n - 1 \le m \le 3 \cdot 10^5 $ ) — the number of locations and passages, respectively.

Then $ m $ lines follow, each containing two integers $ x $ and $ y $ ( $ 1 \le x, y \le n $ , $ x \ne y $ ) describing the endpoints of one of the passages.

It is guaranteed that there is no pair of locations directly connected by two or more passages, and that any location is reachable from any other location.

输出格式

Print one integer — the maximum number of bosses your friend can place, considering all possible choices for $ s $ and $ t $ .

样例 #1

样例输入 #1

5 5
1 2
2 3
3 1
4 1
5 2

样例输出 #1

2

样例 #2

样例输入 #2

4 3
1 2
4 3
3 2

样例输出 #2

3

解析

（可以手切的紫题...）
这道题非常好想，两个步骤就可以解决，边双缩点和求树的直径。
先用tarjan找到割边，再跑一遍dfs划分连通块，这时候我们得到一棵树，按照题意，我们要求的答案就是树的直径，这里我用的dp求直径。

代码

#include <bits/stdc++.h>
using namespace std;
const int N = 3e5 + 10;
int tot = 1, head[N], nxt[N << 1], to[N << 1];
int n, m, dfn[N], low[N], bel[N], way[N << 1], cnt, idx;
vector<int> e[N];
void add(int x, int y) {
	nxt[++ tot] = head[x]; head[x] = tot; to[tot] = y;
}
void tarjan(int u, int fa) {//找割边 
	dfn[u] = low[u] = ++ cnt;
	for (int i = head[u]; i; i = nxt[i]) {
		int v = to[i];
		if (!dfn[v]) {
			tarjan(v, i);
			low[u] = min(low[u], low[v]);
			if (low[v] > dfn[u]) way[i] = way[i ^ 1] = 1;
		}
		else if ((i ^ 1) != fa) low[u] = min(low[u], dfn[v]);
	}
}
void dfs(int u) {//划分成多个连通块 
	bel[u] = idx;
	for (int i = head[u]; i; i = nxt[i]) {
		int v = to[i];
		if (bel[v] || way[i]) continue;
		dfs(v);
	}
}
int ans, f1[N], f2[N];
void dp(int u, int fa) {//dp求树的直径 
	for (int i = 0; i < e[u].size(); i ++) {
		int v = e[u][i];
		if (v == fa) continue;
		dp(v, u);
		if (f1[u] < f1[v] + 1) {
			f2[u] = f1[u];
			f1[u] = f1[v] + 1;
		}
		else if (f2[u] < f1[v] + 1) f2[u] = f1[v] + 1;
		ans = max(ans, f1[u] + f2[u]);
	}
}
int main() {
	cin >> n >> m;
	for (int i = 1; i <= m; i ++) {
		int x, y; cin >> x >> y;
		add(x, y), add(y, x);
	}
	tarjan(1, 0);
	for (int i = 1; i <= n; i ++) 
		if (!bel[i]) {idx ++, dfs(i);}
	for (int i = 1; i <= n; i ++) {
		for (int j = head[i]; j; j = nxt[j]) {
			int v = to[j];
			if (bel[i] == bel[v]) continue;
			e[bel[i]].push_back(bel[v]);
		}
	}
	for (int i = 1; i <= idx; i ++) {//去掉重复的边 
		sort(e[i].begin(), e[i].end());
		unique(e[i].begin(), e[i].end());
	}
	dp(1, 0);
	cout << ans << '\n';
	return 0;
}