题解 | #DongDong认亲戚#

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)
}