并查集---We Are A Team

题目描述
总共有 n 个人在机房，每个人有一个标号（1<=标号<=n），他们分成了多个团队，需要你根据收到的 m 条消息判定指定的两个人是否在一个团队中，具体的：

消息构成为 a b c，整数 a、b 分别代表两个人的标号，整数 c 代表指令

c == 0 代表 a 和 b 在一个团队内
c == 1 代表需要判定 a 和 b 的关系，如果 a 和 b 是一个团队，输出一行’we are a team’,如果不是，输出一行’we are not a team’
c 为其他值，或当前行 a 或 b 超出 1~n 的范围，输出‘da pian zi’
输入描述
第一行包含两个整数 n，m(1<=n,m<100000),分别表示有 n 个人和 m 条消息

随后的 m 行，每行一条消息，消息格式为：a b c(1<=a,b<=n,0<=c<=1)

输出描述
c ==1,根据 a 和 b 是否在一个团队中输出一行字符串，在一个团队中输出‘we are a team‘,不在一个团队中输出’we are not a team’

c 为其他值，或当前行 a 或 b 的标号小于 1 或者大于 n 时，输出字符串‘da pian zi‘

如果第一行 n 和 m 的值超出约定的范围时，输出字符串”NULL“。

用例1
输入
5 7
1 2 0
4 5 0
2 3 0
1 2 1
2 3 1
4 5 1
1 5 1
输出
we are a team
we are a team
we are a team
we are not a team
用例2
输入
5 6
1 2 0
1 2 1
1 5 0
2 3 1
2 5 1
1 3 2
输出
we are a team
we are not a team
we are a team
da pian zi

n,m = map(int,input().split())
mages = [list(map(int,input().split())) for _ in range(m)]
#实现一下并查集
class Union:
    def __init__(self,n):
        self.parent = [i for i in range(n)]

    def find(self,x):
        if self.parent[x] !=x:
            self.parent[x] = self.find(self.parent[x])# 路径压缩
            return  self.parent[x]
        return x

    def union(self,x,y):
        x_parent = self.find(x)
        y_parent = self.find(y)
        if x_parent != y_parent:
            self.parent[y_parent] = x_parent
def get_reslut():
    if n<1 or n>=100000 or m<1 or m>=100000:
        print('NULL')
        return
    ufs = Union(n+1)
    for a,b,c in mages:
        if a<1 or a>n or b<1 or b>n:
            print('da pian zi')
            continue
        if c==0:
            ufs.union(a,b)
        elif c==1:
            if ufs.find(a)==ufs.find(b):
                print('we are a team')
            else:
                print('we are not a team')
        else:
            print('da pian zi')

get_reslut()```

原文地址：https://blog.csdn.net/TTz012/article/details/142921628

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！