lessons/参考实现/02-强连通与双连通/AtCoder-agc071_c.cpp

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

struct Edge {
    int to;
    int id;
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int tests;
    cin >> tests;
    while (tests--) {
        int n, m;
        cin >> n >> m;
        vector<pair<int, int>> ends(m);
        vector<vector<Edge>> graph(n);
        for (int id = 0; id < m; ++id) {
            int u, v;
            cin >> u >> v;
            --u;
            --v;
            ends[id] = {u, v};
            graph[u].push_back({v, id});
            graph[v].push_back({u, id});
        }

        bool bipartite = true;
        vector<int> color(n, -1);
        queue<int> bfs;
        color[0] = 0;
        bfs.push(0);
        while (!bfs.empty()) {
            int u = bfs.front();
            bfs.pop();
            for (Edge e : graph[u]) {
                if (color[e.to] == -1) {
                    color[e.to] = color[u] ^ 1;
                    bfs.push(e.to);
                } else if (color[e.to] == color[u]) {
                    bipartite = false;
                }
            }
        }

        vector<int> dfn(n, 0), low(n, 0), edge_stack;
        vector<vector<int>> groups(n);
        vector<int> parent_vertex(n, -1), parent_edge(n, -1), cursor(n, 0);
        vector<int> incident_count(n, 0), touched;
        int timer = 1;
        dfn[0] = low[0] = 1;
        vector<int> dfs_stack = {0};
        while (!dfs_stack.empty()) {
            int u = dfs_stack.back();
            if (cursor[u] < static_cast<int>(graph[u].size())) {
                Edge e = graph[u][cursor[u]++];
                if (e.id == parent_edge[u]) continue;
                if (!dfn[e.to]) {
                    parent_vertex[e.to] = u;
                    parent_edge[e.to] = e.id;
                    edge_stack.push_back(e.id);
                    dfn[e.to] = low[e.to] = ++timer;
                    dfs_stack.push_back(e.to);
                } else if (dfn[e.to] < dfn[u]) {
                    edge_stack.push_back(e.id);
                    low[u] = min(low[u], dfn[e.to]);
                }
                continue;
            }

            dfs_stack.pop_back();
            int parent = parent_vertex[u];
            if (parent == -1) continue;
            low[parent] = min(low[parent], low[u]);
            if (low[u] < dfn[parent]) continue;

            touched.clear();
            while (true) {
                int id = edge_stack.back();
                edge_stack.pop_back();
                for (int v : {ends[id].first, ends[id].second}) {
                    if (incident_count[v] == 0) touched.push_back(v);
                    ++incident_count[v];
                }
                if (id == parent_edge[u]) break;
            }
            for (int v : touched) {
                groups[v].push_back(incident_count[v]);
                incident_count[v] = 0;
            }
        }

        bool every_degree_is_formable = true;
        for (auto &sizes : groups) {
            sort(sizes.begin(), sizes.end());
            int covered = 0;
            for (int size : sizes) {
                if (size > covered + 1) {
                    every_degree_is_formable = false;
                    break;
                }
                covered += size;
            }
        }
        cout << (!(bipartite && every_degree_is_formable) ? "Yes\n" : "No\n");
    }
    return 0;
}