Submission #64378939

---

Source Code Expand

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

#define all(a) begin(a), end(a)
#define len(a) (int)((a).size())

const int SZ = 200'100;

struct dsu {
    int n, comps = 0;
    vector<int> par, cnt;
    dsu(int n) : n(n) {
        par.resize(n);
        cnt.resize(n);
        for (int i = 0; i < n; ++i) {
            par[i] = i;
        }
    }

    int find(int v) {
        if (par[v] == v) return v;
        return par[v] = find(par[v]);
    }
    void active(int x) {
        ++comps;
        cnt[find(x)]++;
    }
    void uni(int v, int u) {
        v = find(v);
        u = find(u);
        if (v != u) {
            if (cnt[v] && cnt[u]) {
                --comps;
            }
            par[v] = u;
            cnt[u] += cnt[v];
        }
    }
};

int n, m;
vector<vector<int>> gr;

bool bip;
int used[SZ], tin[SZ], low[SZ], t = 0, good[SZ];
vector<int> cur;
void dfs(int v, int col = 0) {
    used[v] = col + 1;
    for (auto to : gr[v]) {
        if (!used[to]) {
            dfs(to, col ^ 1);
        } else if (used[to] - 1 != (col ^ 1)) {
            bip = false;
        }
    }
    cur.push_back(v);
}

dsu unit(0);

void dfs2(int v, int p = -1) {
    used[v] = true;
    tin[v] = low[v] = t++;
    for (int to : gr[v]) {
        if (to == p) continue;
        if (used[to]) {
            low[v] = min(low[v], tin[to]);
        } else {
            dfs2(to, v);
            low[v] = min(low[v], low[to]);
            if (low[to] > tin[v]) {
                good[v]++;
                good[to]++;
                unit.active(v);
                unit.active(to);
            } else {
                unit.uni(to, v);
            }
        }
    }
}

void solve() {
    cin >> n >> m;
    gr.clear();
    gr.resize(n);
    cur.clear();
    unit = dsu(n);
    for (int i = 0; i < n; ++i) {
        used[i] = good[i] = 0;
        tin[i] = low[i] = -1;
        //unit.active(i);
    }
    t = 0;
    for (int i = 0; i < m; ++i) {
        int u, v;
        cin >> u >> v;
        --u; --v;
        gr[u].push_back(v);
        gr[v].push_back(u);
    }

    bip = true;
    for (int i = 0; i < n; ++i) {
        if (!used[i]) {
            dfs(i);
        }
    }

    if (!bip) {
        cout << "Yes\n";
    } else {
        for (int i = 0; i < n; ++i) used[i] = 0;
        bool gd = true; 
        for (int i = 0; i < n; ++i) {
            if (!used[i]) {
                cur.clear();
                dfs2(i);
            }
            gd &= (good[i] >= 1);
            //int cnter = unit.cnt[unit.find(i)];
            gd &= (good[i] * 2 >= len(gr[i]) - good[i] - 1);
        }
        if (!gd) {
            cout << "Yes\n";
        } else {
            cout << "No\n";
        }
    }
}

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

    int t;
    cin >> t;

    while (t--) {
        solve();
    }

    return 0;
} 

Submission Info

Judge Result