hihocoder 1066 并查集

/**/
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cctype>
#include <iostream>
#include <algorithm>
#include <map>
#include <set>
#include <vector>
#include <string>
#include <stack>
#include <queue>

typedef long long LL;
typedef unsigned long long ULL;
using namespace std;

bool Sqrt(LL n) { return (LL)sqrt(n) * sqrt(n) == n; }
const double PI = acos(-1.0), ESP = 1e-10;
const LL INF = 99999999999999;
const int inf = 999999999, N = 1e5 + 5;
int n, op, fa[N], m, x, y;
char s[N];
map<string, int> mp;
int Find(int x)
{
    int y = x;
    for(; x != fa[x]; x = fa[x]);
    return fa[y] = x;
}

int Read()
{
    scanf("%s", s);
    if(mp.count(s)) return mp[s];
    mp[s] = ++m;
    fa[m] = m;
    return m;
}

int main()
{
    //freopen("in.txt", "r", stdin);
    //freopen("out.txt", "w", stdout);
    scanf("%d", &n);
    while(n--) {
        scanf("%d", &op);
        x = Find(Read());
        y = Find(Read());
        if(op) x == y ? puts("yes") : puts("no");
        else fa[x] = y;
    }

    return 0;
}
/*
    input:
    output:
    modeling:
    methods:
    complexity:
    summary:
*/

hihocoder 1066 并查集

原文：https://www.cnblogs.com/000what/p/11674242.html