forked from EndlessCheng/codeforces-go
-
Notifications
You must be signed in to change notification settings - Fork 0
/
547D.go
58 lines (52 loc) · 966 Bytes
/
547D.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
package main
import (
"bufio"
. "fmt"
"io"
)
// https://space.bilibili.com/206214
func cf547D(_r io.Reader, _w io.Writer) {
in := bufio.NewReader(_r)
out := bufio.NewWriter(_w)
defer out.Flush()
var n, x, y int
Fscan(in, &n)
g := make([][]int, n+1)
var preX, preY [2e5 + 1]int
for i := 1; i <= n; i++ {
Fscan(in, &x, &y)
if preX[x] == 0 {
preX[x] = i
} else {
g[i] = append(g[i], preX[x])
g[preX[x]] = append(g[preX[x]], i)
preX[x] = 0
}
if preY[y] == 0 {
preY[y] = i
} else {
g[i] = append(g[i], preY[y])
g[preY[y]] = append(g[preY[y]], i)
preY[y] = 0
}
}
colors := make([]int, n+1)
var dfs func(int, int)
dfs = func(v, c int) {
colors[v] = c
for _, w := range g[v] {
if colors[w] == 0 {
dfs(w, 3^c)
}
}
}
for i := 1; i <= n; i++ {
if colors[i] == 0 {
dfs(i, 1)
}
}
for _, c := range colors[1:] {
Fprintf(out, "%c", " br"[c])
}
}
//func main() { cf547D(os.Stdin, os.Stdout) }