题目大意：给一张无向图，要求找一对$s$和$t$，使得其路径上的割边是最多的，输出其数量。
题解：把边双缩点以后求树的直径。
卡点：无
C++ Code：
#include#include #define maxn 300010#define maxm 300010#define ONLINE_JUDGE#define read() R::READ()#include namespace R { int x; #ifdef ONLINE_JUDGE char *ch, op[1 << 26]; inline void init() { fread(ch = op, 1, 1 << 26, stdin); } inline int READ() { while (isspace(*ch)) ch++; for (x = *ch & 15, ch++; isdigit(*ch); ch++) x = x * 10 + (*ch & 15); return x; } #else char ch; inline int READ() { ch = getchar(); while (isspace(ch)) ch = getchar(); for (x = ch & 15, ch = getchar(); isdigit(ch); ch = getchar()) x = x * 10 + (ch & 15); return x; } #endif}int n, m;inline int min(int a, int b) {return a < b ? a : b;}namespace Tree { int head[maxn], cnt; struct Edge { int to, nxt; } e[maxm << 1]; void add(int a, int b) { e[++cnt] = (Edge) {b, head[a]}; head[a] = cnt; e[++cnt] = (Edge) {a, head[b]}; head[b] = cnt; } int q[maxn], h = 1, t = 0; int d[maxn]; int bfs(int rt) { memset(d, 0, sizeof d); d[q[h = t = 0] = rt] = 1; while (h <= t) { int u = q[h++]; for (int i = head[u]; i; i = e[i].nxt) { int v = e[i].to; if (!d[v]) { d[v] = d[u] + 1; q[++t] = v; } } } return q[t]; } int work() { int x = bfs(1), y = bfs(x); return d[y] - 1; }}namespace Graph { int head[maxn], cnt; struct Edge { int from, to, nxt; } e[maxm << 1]; void add(int a, int b) { e[++cnt] = (Edge) {a, b, head[a]}; head[a] = cnt; e[++cnt] = (Edge) {b, a, head[b]}; head[b] = cnt; } int res[maxn], CNT; int DFN[maxn], low[maxn], idx, fa[maxn]; int S[maxn], top; void Tarjan(int u) { DFN[u] = low[u] = ++idx; S[++top] = u; int v; for (int i = head[u]; i; i = e[i].nxt) { v = e[i].to; if (v == fa[u]) continue; if (!DFN[v]) { fa[v] = u; Tarjan(v); low[u] = min(low[u], low[v]); if (low[v] > DFN[u]) { CNT++; do res[v = S[top--]] = CNT; while (v != e[i].to); } } else low[u] = min(low[u], DFN[v]); } } inline void tarjan(int n) { for (int i = 1; i <= n; i++) if (!DFN[i]) Tarjan(i); } inline void init() { for (int i = 1; i <= cnt; i += 2) { if (res[e[i].from] != res[e[i].to]) Tree::add(res[e[i].from], res[e[i].to]); } }}int main() { #ifdef ONLINE_JUDGE R::init(); #endif n = read(), m = read(); for (int i = 1; i <= m; i++) Graph::add(read(), read()); Graph::tarjan(n); Graph::init(); printf("%d\n", Tree::work()); return 0;}