-
Notifications
You must be signed in to change notification settings - Fork 502
/
b.go
50 lines (46 loc) · 836 Bytes
/
b.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
package main
// github.com/EndlessCheng/codeforces-go
func minimumTeachings(n int, languages, friendships [][]int) (ans int) {
ls := make([]map[int]bool, len(languages))
for i, l := range languages {
ls[i] = map[int]bool{}
for _, v := range l {
ls[i][v] = true
}
}
ok := make([]bool, len(friendships))
for i, e := range friendships {
e[0]--
e[1]--
for v := range ls[e[0]] {
if ls[e[1]][v] {
ok[i] = true
break
}
}
}
ans = 1e9
for l := 1; l <= n; l++ {
taught := map[int]bool{}
for i, e := range friendships {
if ok[i] {
continue
}
v, w := e[0], e[1]
if !ls[v][l] && !taught[v] {
taught[v] = true
}
if !ls[w][l] && !taught[w] {
taught[w] = true
}
}
ans = min(ans, len(taught))
}
return
}
func min(a, b int) int {
if a < b {
return a
}
return b
}