-
Notifications
You must be signed in to change notification settings - Fork 0
/
771a.go
105 lines (98 loc) · 1.47 KB
/
771a.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
// 00
package main
import (
"bufio"
"fmt"
"os"
)
func write(f *bufio.Writer, a ...interface{}) {
f.Write([]byte(fmt.Sprint(a...)))
}
type Number interface {
int64 | float64 | int
}
func min[K Number](a K, b K) K {
if a < b {
return a
}
return b
}
func max[K Number](a K, b K) K {
if a > b {
return a
}
return b
}
func abs[K Number](a K) K {
if a < 0 {
return -a
}
return a
}
type Dsu struct {
p []int
sz []int
components int
}
func (d Dsu) get(x int) int {
if x == d.p[x] {
return x
} else {
d.p[x] = d.get(d.p[x])
return d.p[x]
}
}
func (d Dsu) unite(x int, y int) bool {
x = d.get(x)
y = d.get(y)
if x != y {
if d.sz[x] < d.sz[y] {
x, y = y, x
}
d.sz[x] += d.sz[y]
d.p[y] = x
d.components--
return true
}
return false
}
func (d Dsu) size(x int) int {
return d.sz[d.get(x)]
}
func give_dsu(n int) Dsu {
p := make([]int, n)
sz := make([]int, n)
for i := 0; i < n; i++ {
p[i] = i
sz[i] = 1
}
return Dsu{p, sz, n}
}
func main() {
var n, m int
reader := bufio.NewReader(os.Stdin)
f := bufio.NewWriter(os.Stdout)
defer f.Flush()
fmt.Fscan(reader, &n, &m)
dsu := give_dsu(n + 1)
for i := 0; i < m; i++ {
var u, v int
fmt.Fscan(reader, &u, &v)
dsu.unite(u, v)
}
sizes := make([]int, n+1)
for i := 1; i <= n; i++ {
sizes[dsu.get(i)]++
}
ans := 0
for i := 1; i <= n; i++ {
if sizes[i] > 0 {
ans += (sizes[i] * (sizes[i] - 1)) / 2
}
}
if ans == m {
write(f, "YES\n")
} else {
write(f, "NO\n")
}
}