题解 | #DongDong认亲戚#
DongDong认亲戚
https://ac.nowcoder.com/acm/problem/23803
技巧
并查集
思路
模板题
实现
package main
import (
"bufio"
. "fmt"
"io"
"os"
)
type Node struct {
name string
parent *Node
}
// https://ac.nowcoder.com/acm/problem/23803
func NC23803(_r io.Reader, _w io.Writer) {
in, out := bufio.NewReader(_r), bufio.NewWriter(_w)
defer out.Flush()
var n, m int
Fscan(in, &n, &m)
unionFindSet := make(map[string]*Node)
for i := 0; i < n; i++ {
var name string
Fscan(in, &name)
unionFindSet[name] = &Node{name: name}
}
for i := 0; i < m; i++ {
var opt int
var name1, name2 string
Fscan(in, &opt, &name1, &name2)
if opt == 1 {
union(unionFindSet[name1], unionFindSet[name2])
} else {
Fprintln(out, same(unionFindSet[name1], unionFindSet[name2]))
}
}
}
func getRoot(node *Node) *Node {
if node.parent == nil {
return node
} else {
p := getRoot(node.parent)
node.parent = p
return p
}
}
func same(n1, n2 *Node) int {
if n1 == n2 || getRoot(n1) == getRoot(n2) {
return 1
}
return 0
}
func union(n1, n2 *Node) {
if same(n1, n2) == 0 {
getRoot(n1).parent = n2
}
}
func main() {
NC23803(os.Stdin, os.Stdout)
}
