算法1
并查集
基本思路
并查集先归并所有连边,然后便利剩下的不满足的条件,如若已在同一个group中则说明问题条件相悖。需要注意的是需要对i,j做一次hash映射。且golang不要使用fmt.Scan读取数据,会导致tle
时间复杂度 $O(n*s)$
golang 代码
package main
import (
"bufio"
"fmt"
"os"
"strconv"
"strings"
)
type UnionFind struct {
rank []int
fa []int
}
func NewUnionFind(n int) *UnionFind {
fa := make([]int, n)
rank := make([]int, n)
for i := 0; i < n; i++ {
fa[i] = i
}
return &UnionFind{
rank: rank,
fa: fa,
}
}
func (uf *UnionFind) Find(x int) int {
if x != uf.fa[x] {
uf.fa[x] = uf.Find(uf.fa[x])
}
return uf.fa[x]
}
func (uf *UnionFind) Union(x, y int) {
xroot, yroot := uf.Find(x), uf.Find(y)
if xroot == yroot {
return
}
if uf.rank[xroot] > uf.rank[yroot] {
uf.fa[yroot] = xroot
} else if uf.rank[xroot] < uf.rank[yroot] {
uf.fa[xroot] = yroot
} else {
uf.fa[xroot] = yroot
uf.rank[yroot]++
}
}
type embedding struct {
i int
j int
}
func main() {
var t, cnt int
scanner := bufio.NewScanner(os.Stdin)
if scanner.Scan() {
t, _ = strconv.Atoi(scanner.Text())
}
for t != 0 {
t--
if scanner.Scan() {
n, _ := strconv.Atoi(scanner.Text())
cnt = 0
hash := make(map[int]int, 2*n)
uf := NewUnionFind(2 * n)
var notes []embedding
for n != 0 && scanner.Scan() {
n--
line := scanner.Text()
parts := strings.Fields(line)
i, _ := strconv.Atoi(parts[0])
j, _ := strconv.Atoi(parts[1])
e, _ := strconv.Atoi(parts[2])
if _, ok := hash[i]; !ok {
hash[i] = cnt
cnt++
}
if _, ok := hash[j]; !ok {
hash[j] = cnt
cnt++
}
if e == 0 {
notes = append(notes, embedding{hash[i], hash[j]})
} else if e == 1 {
uf.Union(hash[i], hash[j])
}
}
signal := true
for _, note := range notes {
rootI, rootJ := uf.Find(note.i), uf.Find(note.j)
if rootI == rootJ {
fmt.Println("NO")
signal = false
break
}
}
if signal {
fmt.Println("YES")
}
}
}
}