-
Notifications
You must be signed in to change notification settings - Fork 1
/
a.go
68 lines (52 loc) · 997 Bytes
/
a.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
package main
import (
"bufio"
"fmt"
"os"
)
const (
DDN_FMT = "%d %d\n"
DS_FMT = "%d "
)
func dfs(v int, color int, graph *[][]int, colors *[]int) {
(*colors)[v] = color
for _, u := range (*graph)[v] {
if (*colors)[u] != color {
dfs(u, color, graph, colors)
}
}
}
func solve(fin *os.File, fout *os.File) {
in := bufio.NewReader(fin)
out := bufio.NewWriter(fout)
var n int
var m int
fmt.Fscanf(in, DDN_FMT, &n, &m)
var graph = make([][]int, n)
var b int
var e int
for i := 0; i < m; i++ {
fmt.Fscanf(in, DDN_FMT, &b, &e)
b -= 1
e -= 1
graph[b] = append(graph[b], e)
graph[e] = append(graph[e], b)
}
var colors = make([]int, n)
var max_color = 1
for i := 0; i < n; i++ {
if colors[i] == 0 {
dfs(i, max_color, &graph, &colors)
max_color += 1
}
}
fmt.Fprintf(out, "%d\n", max_color-1)
for i := 0; i < n; i++ {
fmt.Fprintf(out, DS_FMT, colors[i])
}
fmt.Fprintf(out, "\n")
out.Flush()
}
func main() {
solve(os.Stdin, os.Stdout)
}