UVaOJ)12460 Careful teacher

문제: https://uva.onlinejudge.org/index.php?option=onlinejudge&page=show_problem&problem=3891

문제를 간략하게 설명하면 사전에 존재하는 단어들이 주어진 뒤 쿼리가 들어올 때

쿼리에서 들어오는 두 단어를 A와 B라고할 때 A를 B로 바꿀 수 있는지 여부를 물어보는 문제이다.

이 때 A를 B로 바꾸는 경우는 한글자 씩 바꿀 수 있으며 단, 한글자를 바꾼 단어도 사전에 존재하여야만 바꿀 수 있다.

이 문제는 사전에 존재하는 단어들을 정점으로 생각하고 1글자 다른 단어들을 간선으로 묶어주면 

A와 B가 같은 컴포넌트에 존재하는지 여부를 묻는 문제로 변형된다.

이는 disjoint-set을 통하여 해결해줄 수 있다.

N제한이 20000이지만 시간제한이 8초이고.. 데이터가 생각보다 약한것 같기 때문에 N*N으로 merge를 해줄 수 있다.

#include <cstdio>
#include <algorithm>
#include <map>
#include <string>
#include <cstring>
using namespace std;
char a[20010][55];
int n, len[20020], par[20010];
char x[55], y[55];
map<string, int> mp;
int find(int h) {
    return h == par[h] ? h : par[h] = find(par[h]);
}
void merge(int x, int y) {
    x = find(x);
    y = find(y);
    if (x == y)return;
    par[x] = y;
}
int main() {
    while (1) {
        scanf("%s", &a[++n]);
        for (len[n]; a[n][len[n]]; len[n]++) {
            a[n][len[n]];
        }
        if (len[n] == 2 && a[n][0] == '-'&&a[n][1] == '-')
            break;
        mp[a[n]] = n;
    }
    n--;
    for (int i = 1; i <= n; i++)
        par[i] = i;
    for (int i = 1; i <= n; i++) {
        for (int j = i + 1; j <= n; j++) {
            if (len[i] != len[j])continue;
            int cnt = 0;
            for (int k = 0; a[i][k]; k++) {
                if (a[i][k] != a[j][k])
                    cnt++;
            }
            if (cnt == 1)
                merge(i, j);
        }
    }
    while (scanf("%s %s", &x, &y) != EOF) {
        if (mp.find(x) == mp.end() || mp.find(y) == mp.end()) {
            puts("No");
            continue;
        }
        int xx = mp[x];
        int yy = mp[y];
        printf("%s\n", find(xx) == find(yy) ? "Yes" : "No");
    }
    return 0;
}