-
Notifications
You must be signed in to change notification settings - Fork 0
/
9.go
82 lines (75 loc) · 1.27 KB
/
9.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
package dfs
import (
"fmt"
"log"
)
type Rewrite struct {
N, M int
graph [][]int
}
func (r *Rewrite) inputFunc() {
inputNumber := func() int {
var number int
_, err := fmt.Scan(&number)
if err != nil {
log.Fatal(err)
}
return number
}
inputArr := func(lenArr int) []int {
var arr = make([]int, lenArr)
for i := 0; i < len(arr); i++ {
_, err := fmt.Scan(&arr[i])
if err != nil {
log.Fatal(err)
}
}
return arr
}
r.N, r.M = inputNumber(), inputNumber()
r.graph = make([][]int, r.N+1)
for i := 0; i < r.M; i++ {
pair := inputArr(2)
i, j := pair[0], pair[1]
r.graph[i] = append(r.graph[i], j)
r.graph[j] = append(r.graph[j], i)
}
}
func (r *Rewrite) process() {
visited := make([]int, r.N+1)
hasCycle := false
var dfs func(int, int)
dfs = func(v, color int) {
if hasCycle {
return
}
visited[v] = color
for _, vn := range r.graph[v] {
if visited[vn] == 0 {
dfs(vn, 3-color)
} else {
if visited[v] == visited[vn] {
hasCycle = true
}
}
}
}
for i := 1; i <= r.N; i++ {
if hasCycle {
break
}
if visited[i] == 0 {
dfs(i, 1)
}
}
if hasCycle {
fmt.Println("NO")
} else {
fmt.Println("YES")
}
}
func RewriteProcessing() {
solution := &Rewrite{}
solution.inputFunc()
solution.process()
}