题解 | #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)
}


全部评论

相关推荐

用户64975461947315:这不很正常吗,2个月开实习证明,这个薪资也还算合理,深圳Java好多150不包吃不包住呢,而且也提前和你说了没有转正机会,现在贼多牛马公司骗你说毕业转正,你辛辛苦苦干了半年拿到毕业证,后面和你说没hc了😂
点赞 评论 收藏
分享
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务