M27306: 植物观察

disjoint set, bfs, http://cs101.openjudge.cn/practice/27306/

周末，小明和他的朋友们去野外观察植物，并拍了 n 张植物的照片回来。社团的前辈告诉他们，照片上所有这些植物都属于两个不同种类 A、B 中的某一种。由于是新手，小明很难直接判断每张照片上的植物属于哪个种类。但是，如果把植物的照片两两组合对比来看，小明能够判断其中一些组合的两个植物是属于相同还是不同的种类。经过一番研究，小明最终得出了 m 组这样的结论。他希望知道，这 m 组结论是否可能同时成立。具体来说，是否存在一种给每个植物分类为 A 或 B 的方法，使得小明的每组结论对于两个植物种类相同或不同的判断均正确。

输入

第一行为两个整数，分别是植物的数量 n 和结论的个数 m。n <= 100, m <= 10000

接下来 m 行，每行为一个结论，包括三个整数，前两个整数表示植物的编号（从 0 到 n-1），第三个整数表示小明的判断，0 代表相同，1 代表不同。

输出

如果所有结论可能同时成立，输出 “YES”，否则输出 “NO”。

样例输入

Sample1 Input:
3 3
0 1 0
1 2 1
0 2 1

Sample1 Output:
YES

解释：分类方案：植物0：A，植物1：A，植物2：B，能够使所有结论同时成立。

样例输出

Sample2 Input:
3 3
0 1 0
1 2 1
0 2 0

Sample2 Output:
NO

解释：所有结论不可能同时成立。

提示

tag: disjoint set, bfs

来源

2023fall zyn

【林茂融 2025fall-cs201 城市与环境学院】思路：这道题是很典型的并查集，课上也提到过。实际上，标记为0的就是边，1的只要单独记录，把边union以后检查标记为1的元素是否连通就行了。考试的时候快速AC了。

python

n, m = map(int, input().split())
parent=[i for i in range(n)]
edges=[]
diff=[]
for _ in range(m):
    a, b, c = map(int, input().split())
    if c!=1:
        edges.append((a, b))
    else:
        diff.append((a, b))

def find(x):
    if parent[x] != x:
        parent[x] = find(parent[x])
    return parent[x]
def union(x, y):
    nx, ny = find(x), find(y)
    if nx != ny:
        parent[ny] = nx
        #return True
    #return False

for a, b in edges:
    union(a, b)

for a, b in diff:
    if find(a) == find(b):
        print('NO')
        exit()
print('YES')

python

class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0] * n

    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]

    def union(self, x, y):
        root_x = self.find(x)
        root_y = self.find(y)
        if root_x != root_y:
            if self.rank[root_x] > self.rank[root_y]:
                self.parent[root_y] = root_x
            elif self.rank[root_x] < self.rank[root_y]:
                self.parent[root_x] = root_y
            else:
                self.parent[root_y] = root_x
                self.rank[root_x] += 1

def can_classify_plants(n, relations):
    uf = UnionFind(n * 2)
    for x, y, relation in relations:
        if relation == 0:  # Same group
            if uf.find(x) == uf.find(y + n) or uf.find(y) == uf.find(x + n):
                return "NO"
            uf.union(x, y)
            uf.union(x + n, y + n)
        else:  # Different groups
            if uf.find(x) == uf.find(y):
                return "NO"
            uf.union(x, y + n)
            uf.union(y, x + n)
    return "YES"

# Input
n, m = map(int, input().split())
relations = [tuple(map(int, input().split())) for _ in range(m)]

# Output
print(can_classify_plants(n, relations))

M27306: 植物观察 ​

M27306: 植物观察