P5836 [USACO19DEC] Milk Visits S - 洛谷题解

 题目链接 ：[P5836] USACO19DEC] Milk Visits S - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

这道题可以用并查集来解决。 题目中每个结点只有两个状态：H和G。那么我们可以推断出，只有当起点和终点间每个结点的状态相同但是起点（或者终点或起点到终点之间的某一点）与所需状态不同才可以输出0。

我们利用并查集来设置连通块，状态相同并且相连的两个结点合并成一个合集，最终查找起点和终点是否在同一合集以查看他们之间是否为同一连通块。 之后通过前面讲过的方法来得到结果。

#include<cstdio>
using namespace std;
int n, m;
int f[100005];

int Find(int x) {
    return x == f[x] ? x : f[x] = Find(f[x]);
}
void merge(int a, int b) {
    f[Find(a)] = Find(b);
}

int main() {
    scanf("%d %d", &n, &m);
    getchar();
    char farm[n + 1];
    for(int i = 1; i <= n; i++) {
        f[i] = i;
        scanf("%c", farm + i);
    }
    for(int i = 1; i < n; i++) {
        int a, b;scanf("%d %d", &a, &b);
        /* 设置连接块 */
        if(farm[a] == farm[b]) merge(a, b); 
    }
    for(int i = 1; i <= m; i++) {
        int a, b;char c;scanf("%d %d %c", &a, &b, &c);
        /*只有当起点和终点间每个结点的状态相同但是起点（或者终点或起点到终点之间的某一点）
        与所需状态不同才可以输出0。*/
        if(Find(a) == Find(b) && farm[a] != c) putchar('0');
        else putchar('1');
    }
    return 0;
}