用并查集维护，并记录之前是否形成过基环树。

对于每次建立连接的操作，判断节点 $u$ 和节点 $v$ 是否已经连通：

• 如果已经连通，并且连通块之前没有形成过基环树，则该连通块中添加这条边满足条件输出 Yes。
• 如果不连通，则将 $u$ 和 $v$ 所在的连通块合并。

AC代码

#include <bits/stdc++.h>
using namespace std;

struct DSU {
    std::vector<int> p, siz;
    DSU(int n) : p(n+1), siz(n+1, 1) { std::iota(p.begin(), p.end(), 0); }
    int find(int x) {
        return p[x] == x ? x : p[x] = find(p[x]);
    }
    bool same(int x, int y) { return find(x) == find(y); }
    bool merge(int x, int y) {
        x = find(x);
        y = find(y);
        if (x == y) return false;
        siz[x] += siz[y];
        p[y] = x;
        return true;
    }
    int size(int x) { return siz[find(x)]; }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n, m;
    cin >> n >> m;
    set<int> st;
    set<pair<int, int>> g;
    DSU d(n);
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        if(u == v) continue;
        if (g.count({u, v}) || g.count({v, u})) {
            cout << "No\n";
            continue;
        }
        if (d.find(u) != d.find(v)) {
            d.merge(u, v);
            cout << "No\n";
        } else {
            int fa = d.find(u);
            if (st.count(fa))
                cout << "No\n";
            else {
                cout << "Yes\n";
                d.merge(u, v);
                st.insert(fa);
            }
        }
        g.insert({u, v});
        g.insert({v, u});
    }
    return 0;
}

java

import java.util.*;

class DSU {
    private int[] p, siz;

    // 构造函数
    public DSU(int n) {
        p = new int[n + 1];
        siz = new int[n + 1];
        Arrays.fill(siz, 1);
        for (int i = 0; i <= n; i++) {
            p[i] = i;
        }
    }

    // 查找函数（带路径压缩）
    public int find(int x) {
        if (p[x] == x) {
            return x;
        } else {
            p[x] = find(p[x]);
            return p[x];
        }
    }

    // 判断两个节点是否在同一个集合
    public boolean same(int x, int y) {
        return find(x) == find(y);
    }

    // 合并两个集合
    public boolean merge(int x, int y) {
        x = find(x);
        y = find(y);
        if (x == y) return false;
        siz[x] += siz[y];
        p[y] = x;
        return true;
    }

    // 获取集合的大小
    public int size(int x) {
        return siz[find(x)];
    }
}

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int m = scanner.nextInt();

        Set<Integer> st = new HashSet<>();
        Set<String> g = new HashSet<>();
        DSU dsu = new DSU(n);

        for (int i = 0; i < m; i++) {
            int u = scanner.nextInt();
            int v = scanner.nextInt();

            if (u == v) continue; // 忽略自环边

            String edge = u < v ? u + "," + v : v + "," + u;
            if (g.contains(edge)) {
                System.out.println("No");
                continue;
            }

            if (!dsu.same(u, v)) {
                dsu.merge(u, v);
                System.out.println("No");
            } else {
                int fa = dsu.find(u);
                if (st.contains(fa)) {
                    System.out.println("No");
                } else {
                    System.out.println("Yes");
                    dsu.merge(u, v);
                    st.add(fa);
                }
            }
            g.add(edge);
        }
        scanner.close();
    }
}

小红的林地

问题描述

小红想在 $n$ 个节点间建立通道，并询问每次添加通道后，所连接的两个节点是否属于形成基环树的连通块。基环树定义为具有 $n$ 个节点和 $n$ 条边的无向连通图，不包含重边和自环。

输入格式

第一行包含两个正整数 $n$ 和 $m$，$n$ 代表节点数量，$m$ 代表小红计划建立的通道数量。

接下来 $m$ 行，每行输入两个正整数 $u$ 和 $v$，代表建立的通道连接节点 $u$ 和节点 $v$。

输出格式

对于每次建立的通道，输出一行结果。如果节点 $u$ 和节点 $v$ 所在的连通块形成了一棵基环树，则输出 Yes，否则输出 No。

样例输入

5 5
1 2
1 3
2 3
4 5
4 5

样例输出

No
No
Yes
No
No

评测数据与规模

• $1 \leq n, m \leq 10^5$
• $1 \leq u, v \leq n$
• $u \neq v$