题解 | #Call to your teacher#

注意到给出的关系是有向的，也就是说不可以直接用并查集将两个元素合并到一个集合内

举个例子，假设 n = 2 ，那么 1 有 2 的电话号码是合法的， 2 有 1 的电话号码是不合法的

解释一下就是，如果老师有我的电话号码，而我没有老师的电话号码，那么这时我是不可能给老师打电话的

因此不能直接合并集合

考虑拆点的做法

我们把一个元素拆成两个，分别代表入点和出点

如果 u 有 v 的电话号码， 我们就把 u 的出点和 v 的入点合并至一个集合（u 打电话给 v）

同时，在初始化时，我们也要把 u 的出点和入点合并（可以理解成 u 转接电话的过程）

最后查询 1 的出点与 n 的入点是否在同一集合

#include <iostream>
using namespace std;

int fa[100010];
int find(int x) {return x==fa[x]?x:(fa[x]=find(fa[x]));}
void merge(int u, int v) {
    u = find(u); v = find(v);
    if (u!=v) fa[u] = v;
}

int main() {
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= 2*n; i ++) fa[i] = i; // i 表示入点 i+N 表示出点
    for (int i = 2; i < n; i ++) merge(i, i + n);
    for (int i = 1, u, v; i <= m; i ++) {
        cin >> u >> v;
        merge(u + n, v);
    }
    if (find(1+n) == find(n)) cout << "Yes";
    else cout << "No";
    return 0;
}