---
tags: uva
---
# Uva12363 - Hedge Mazes
## 題目大意
給一無向圖，題目要我們找出從 A 到 B 是否存在一條路可以互聯
## 重點觀念
- 並差集
## 分析
- 用並差集分群，若為同一群則有，不同群則無
## 程式題目碼

#include <string.h>

#include <iostream>
#include <vector>
using namespace std;

vector<int> graph[10001];
int visit[10001], level[10001], flag[10001], visit_count;

int findset(int v) {
    if (!flag[v] || flag[v] == v) {
        return v;
    } else {
        return findset(flag[v]);
    }
}

void unionset(int a, int b) {
    a = findset(a), b = findset(b);
    if (a < b) swap(a, b);
    flag[b] = a;
}

void dfs(int past, int cur) {
    visit[cur] = level[cur] = ++visit_count;
    for (auto i = graph[cur].begin(); i != graph[cur].end(); i++) {
        if (!visit[*i]) {
            dfs(cur, *i);
            level[cur] = min(level[cur], level[*i]);
            if (level[*i] > visit[cur]) {
                unionset(cur, *i);
            }
        } else if (*i != past) {
            level[cur] = min(level[cur], visit[*i]);
        }
    }
}

int main() {
    int r, c, q;
    while (cin >> r >> c >> q, r > 1) {
        memset(visit, 0, sizeof(visit));
        memset(flag, 0, sizeof(flag));
        memset(level, 0, sizeof(level));
        int visit_count = 0;
        for (int i = 0; i < r; i++) {
            graph[i].clear();
        }
        while (c--) {
            int start, end;
            cin >> start >> end;
            start--, end--;
            graph[start].push_back(end);
            graph[end].push_back(start);
        }
        for (int i = 0; i < r; i++) {
            if (!visit[i]) {
                dfs(i, i);
            }
        }

        while (q--) {
            int a, b;
            cin >> a >> b;
            a--, b--;
            cout << (findset(a) == findset(b) ? "Y" : "N") << endl;
        }
        cout << "-" << endl;
    }

    return 0;
}