洛谷 P1330 封锁阳光大学

// ★★ P1330 正解：**二分图染色，每个连通块各自取 min(黑, 白)**。
//
// 先把题目翻译成一句话：
//   「封锁所有道路」= 每条边**至少**一个端点被选；
//   「不发生冲突」  = 每条边**至多**一个端点被选；
//   ⇒ 合起来：**每条边恰好一个端点被选** ⇒ 这就是一个二分图染色。
//
// 于是：
//   · 一个连通块染成黑白两色，冲突（相邻同色）⇒ 有奇环 ⇒ **Impossible**；
//   · 染得成，就在这个块里取 **min(黑数, 白数)**；
//   · ★★ **各个连通块互不影响，所以是「每块各取 min 再求和」**，不是全局取 min。
//
// ⚠ 题面**没有保证图是连通的** —— 只从 1 号点搜是本页第一个错法。
// ⚠ 题面只保证「没有重边」，**一个字都没说没有自环**。自环意味着一个点和自己相邻
//   ⇒ 必然 Impossible，而这一版天然处理得了（v == u 且已染色同色）。见 p1330Self.cpp。
//
// 复杂度 O(n + m)。顶格 n = 10⁴、m = 10⁵。孤立点自成一块，min(1, 0) = 0，白送。

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

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

    int n, m;
    if (!(cin >> n >> m)) return 0;
    vector<vector<int>> g(n + 1);
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);                            // 无向图，两遍
    }

    vector<int> col(n + 1, -1), st;
    long long ans = 0;
    for (int s = 1; s <= n; s++) {
        if (col[s] != -1) continue;                   // ★ 每个连通块都要来一次
        int cnt[2] = {0, 0};
        st.clear(); st.push_back(s); col[s] = 0;
        while (!st.empty()) {
            int u = st.back(); st.pop_back();
            cnt[col[u]]++;
            for (int v : g[u]) {
                if (col[v] == -1) { col[v] = col[u] ^ 1; st.push_back(v); }
                else if (col[v] == col[u]) { printf("Impossible\n"); return 0; }
            }
        }
        ans += min(cnt[0], cnt[1]);                   // ★★ 每块各取 min
    }
    printf("%lld\n", ans);
    return 0;
}

// ✗ P1330 错法一：**只从 1 号点搜一次** —— 忘了图可能不连通。
//
// 题面从头到尾没说「阳光大学的校园是连通的」。一旦有第二个连通块，
// 它的道路根本没被封锁，答案偏小（而且它连那个块里有没有奇环都不知道）。
//
// ★ 恒 ≤ 正解（漏掉的块只会让答案更小），⚠ 而且它**可能把 Impossible 漏报成一个数**。

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    if (!(cin >> n >> m)) return 0;
    vector<vector<int>> g(n + 1);
    for (int i = 0; i < m; i++) { int u, v; cin >> u >> v; g[u].push_back(v); g[v].push_back(u); }

    vector<int> col(n + 1, -1), st;
    int cnt[2] = {0, 0};
    st.push_back(1); col[1] = 0;                      // ★ 只有 1 号点
    while (!st.empty()) {
        int u = st.back(); st.pop_back();
        cnt[col[u]]++;
        for (int v : g[u]) {
            if (col[v] == -1) { col[v] = col[u] ^ 1; st.push_back(v); }
            else if (col[v] == col[u]) { printf("Impossible\n"); return 0; }
        }
    }
    printf("%d\n", min(cnt[0], cnt[1]));
    return 0;
}

// ✗ P1330 错法二：每个连通块都搜了，可**黑白是全局累加的，最后才取一次 min**。
//
// 这等于强行要求「所有块都选同一种颜色」。而各个块**互不影响** ——
// 这个块选黑、那个块选白，完全合法。
//
// ★ 它给出的是一个**真做得到的方案**（每块都选同一色仍然合法）⇒ 答案**恒 ≥ 正解**。
//   ⇒ 这正是[第 26 章那条判据](/sol/p1220/)：给出一个合法方案 ⇒ 恒 ≥ 最优。

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    if (!(cin >> n >> m)) return 0;
    vector<vector<int>> g(n + 1);
    for (int i = 0; i < m; i++) { int u, v; cin >> u >> v; g[u].push_back(v); g[v].push_back(u); }

    vector<int> col(n + 1, -1), st;
    long long tot[2] = {0, 0};                        // ★ 全局两个桶
    for (int s = 1; s <= n; s++) {
        if (col[s] != -1) continue;
        st.clear(); st.push_back(s); col[s] = 0;
        while (!st.empty()) {
            int u = st.back(); st.pop_back();
            tot[col[u]]++;
            for (int v : g[u]) {
                if (col[v] == -1) { col[v] = col[u] ^ 1; st.push_back(v); }
                else if (col[v] == col[u]) { printf("Impossible\n"); return 0; }
            }
        }
    }
    printf("%lld\n", min(tot[0], tot[1]));            // ★ 最后才取一次 min
    return 0;
}

// ✗ P1330 错法三：染色时**顺手跳过自环**（`if (v == u) continue;`）。
//
// 看着像一句无害的防御 —— 很多模板里都有。可这道题里它是致命的：
// 一个自环意味着「这个点和自己相邻」⇒ 它被封锁就冲突、不封锁就漏了一条路
// ⇒ **答案必然是 Impossible**，而跳过它就把这件事咽了下去，照常打出一个数。
//
// ⚠⚠ 而题面只写了「保证**没有重边**」—— **一个字都没说没有自环**。
//   解析页第 ⑤ 步把这两件事分开量了一遍：
//   **重边对每一个版本都毫无影响（噪声），自环是这个写法的命门。**

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    if (!(cin >> n >> m)) return 0;
    vector<vector<int>> g(n + 1);
    for (int i = 0; i < m; i++) { int u, v; cin >> u >> v; g[u].push_back(v); g[v].push_back(u); }

    vector<int> col(n + 1, -1), st;
    long long ans = 0;
    for (int s = 1; s <= n; s++) {
        if (col[s] != -1) continue;
        int cnt[2] = {0, 0};
        st.clear(); st.push_back(s); col[s] = 0;
        while (!st.empty()) {
            int u = st.back(); st.pop_back();
            cnt[col[u]]++;
            for (int v : g[u]) {
                if (v == u) continue;                 // ★ 就是这一句
                if (col[v] == -1) { col[v] = col[u] ^ 1; st.push_back(v); }
                else if (col[v] == col[u]) { printf("Impossible\n"); return 0; }
            }
        }
        ans += min(cnt[0], cnt[1]);
    }
    printf("%lld\n", ans);
    return 0;
}