-
Notifications
You must be signed in to change notification settings - Fork 519
/
1000E.go
107 lines (100 loc) · 1.81 KB
/
1000E.go
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
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
package main
import (
"bufio"
. "fmt"
"io"
)
// 另一种写法,不需要缩点 https://codeforces.com/problemset/submission/1000/83364650
// github.com/EndlessCheng/codeforces-go
func CF1000E(_r io.Reader, out io.Writer) {
in := bufio.NewReader(_r)
min := func(a, b int) int {
if a < b {
return a
}
return b
}
type neighbor struct{ to, eid int }
type edge struct{ v, w int }
var n, m, v, w, u, ans int
Fscan(in, &n, &m)
g := make([][]neighbor, n)
edges := make([]edge, m)
for i := 0; i < m; i++ {
Fscan(in, &v, &w)
v--
w--
g[v] = append(g[v], neighbor{w, i})
g[w] = append(g[w], neighbor{v, i})
edges[i] = edge{v, w}
}
isBridge := make([]bool, m)
dfn := make([]int, n)
dfsClock := 0
var f func(v, fa int) int
f = func(v, fa int) int {
dfsClock++
dfn[v] = dfsClock
lowV := dfsClock
for _, e := range g[v] {
w := e.to
if dfn[w] == 0 {
lowW := f(w, v)
if lowW > dfn[v] {
isBridge[e.eid] = true
}
lowV = min(lowV, lowW)
} else if w != fa && dfn[w] < dfn[v] {
lowV = min(lowV, dfn[w])
}
}
return lowV
}
for i, t := range dfn {
if t == 0 {
f(i, -1)
}
}
ids := make([]int, n)
idCnt := 0
var f2 func(int)
f2 = func(v int) {
ids[v] = idCnt
for _, e := range g[v] {
if w := e.to; ids[w] == 0 && !isBridge[e.eid] {
f2(w)
}
}
}
for i, id := range ids {
if id == 0 {
idCnt++
f2(i)
}
}
t := make([][]int, idCnt+1)
for _, e := range edges {
if v, w := ids[e.v], ids[e.w]; v != w {
t[v] = append(t[v], w)
t[w] = append(t[w], v)
}
}
var f3 func(v, fa, d int)
f3 = func(v, fa, d int) {
if d > ans {
ans = d
u = v
}
for _, w := range t[v] {
if w != fa {
f3(w, v, d+1)
}
}
}
ans = -1
f3(1, 0, 0)
ans = -1
f3(u, 0, 0)
Fprint(out, ans)
}
//func main() { CF1000E(os.Stdin, os.Stdout) }