Codeforces 1000E(Tarjan缩边-双连通分量+树的直径)

Codeforces 1000E
题意:一条路径上必经的边为关键边,现在让你找一条路径,使得其关键边最多,输出最多的数量。
关键边就是无向图中的桥。而桥两边连的连通分量里面不可能有关键边(桥),所以用 Tarjan 缩边-双连通分量,步骤与有向图相似。然后缩点后就只需要找一条路径最长了,因为缩点了所以最后出来的图就是一个树,所以求树的直径即可。
知识点:
1、一样的代码不要复制,手打
2、缩点,树剖,单调队列注意前后序号的不同,一定要一个字符一个字符的查
3、树的直径就是树中最长路径,长度是树中点对最短距离的最长距离
4、无向图 Tarjan 缩连通分量,留下的边是桥

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<vector>
#include<climits>
#include<stack>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
using std::cin; using std::cout; using std::endl;
const int MAXN = 300000 + 5;
struct edge {int v, nxt;} ed[MAXN * 2], ED2[MAXN * 2];
int n, m, en, EN2, hd[MAXN], HD2[MAXN];
int bcc_tot, bcc_belong[MAXN], sz, dfn[MAXN], low[MAXN];
std::stack<int > s;
void ins(int x, int y) {ed[++en] = (edge){y, hd[x]}, hd[x] = en;}
void INS2(int x, int y) {ED2[++EN2] = (edge){y, HD2[x]}, HD2[x] = EN2;}
void tarjan(int u, int fa) {
dfn[u] = low[u] = ++sz, s.push(u);
for (int i = hd[u]; i > 0; i = ed[i].nxt) {
edge &e = ed[i];
if (e.v == fa) continue;
if (!dfn[e.v]) tarjan(e.v, u), low[u] = std::min(low[u], low[e.v]);
else low[u] = std::min(low[u], dfn[e.v]);//这里最好加上判断是否在栈里,不写也能过 QAQ
}
if (low[u] == dfn[u]) {
int e; bcc_tot++;
do {
e = s.top(); s.pop();
bcc_belong[e] = bcc_tot;
} while (e != u);
}
}
int dis[MAXN];
void dfs(int u, int fa) {
dis[u] = dis[fa] + 1;
for (int i = HD2[u]; i > 0; i = ED2[i].nxt) {
edge &e = ED2[i];
if (e.v != fa) dfs(e.v, u);
}
}
void clean() {
en = EN2 = 0;
ms(hd, 0), ms(HD2, 0);
scc_tot = sz = 0, ms(dfn, 0);
}
int solve() {
clean();
for (int x, y, i = 1; i <= m; i++) scanf("%d%d", &x, &y), ins(x, y), ins(y, x);
for (int i = 1; i <= n; i++) if (!dfn[i]) tarjan(i, 0);
for (int u = 1; u <= n; u++) {
for (int i = hd[u]; i > 0; i = ed[i].nxt) {
edge &e = ed[i];
if (bcc_belong[u] != bcc_belong[e.v]) INS2(bcc_belong[u], bcc_belong[e.v]);
}
}
ms(dis, 0); dfs(1, 0);
int S = 1; for (int i = 2; i <= bcc_tot; i++) if (dis[i] > dis[S]) S = i;
dfs(S, 0);
int T = 1; for (int i = 2; i <= bcc_tot; i++) if (dis[i] > dis[T]) T = i;
printf("%d\n", dis[T] - 1);
return 0;
}
int main() {
scanf("%d%d", &n, &m), solve();
return 0;
}
------ 本文结束 ------