Luogu P1330 – 图的遍历

PROBLEM

https://www.luogu.org/problemnew/show/P1330

ANALYSIS

用不相邻的x 的点，切断所有的边。不存在则输出Impossible 。

有点意思的一个题。直接思考可能比较困难，转化为 用两种颜色对全图所有点染色，且相邻点颜色不同 的话，就可以轻松解决了。

以下为深搜和宽搜两种解法。

SOLUTION

// 152ms /  2.63MB
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <queue>

using namespace std;

const int N = 11000;

vector<int> a[N];
queue<int> q;
int n, m, cnt;
int c[N], f[2], s;

void try_dfs(int x, int w) {
    c[x] = w;
    f[w]++;
    s++;
    for (auto e : a[x]) {
        if (!~c[e]) {
            try_dfs(e, c[x] ^ 1);
        } else if (c[e] == w) {
            throw 1;
            return;
        }
    }
}

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 0, e, f; i < m; i++) {
        scanf("%d%d", &e, &f);
        a[e].push_back(f);
        a[f].push_back(e);
    }
    memset(c, -1, sizeof(c));
    while (s != n) {
        f[0] = f[1] = 0;
        for (int i = 1; i <= n; i++) {
            if (!~c[i]) {
                try {
                    try_dfs(i, 0);
                } catch (...) {
                    cout << "Impossible" << endl;
                    return 0;
                }
                cnt += min(f[1], f[0]);
                break;
            }
        }
    }
    cout << cnt << endl;
    return 0;
}

#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <queue>

using namespace std;

const int N = 11000;

vector<int> a[N];
queue<int> q;
int n, m, cnt;
int c[N], f[2], s;

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 0, e, f; i < m; i++) {
        scanf("%d%d", &e, &f);
        a[e].push_back(f);
        a[f].push_back(e);
    }
    memset(c, -1, sizeof(c));
    while (s != n) {
        f[0] = f[1] = 0;
        for (int i = 1; i <= n; i++) {
            if (!~c[i]) {
                q.push(i);
                c[i] = 0;
                f[0]++;
                s++;
                break;
            }
        }
        int u;
        while (!q.empty()) {
            u = q.front();
            for (auto e : a[u]) {
                if (!~c[e]) {
                    c[e] = c[u] ^ 1;
                    s++;
                    f[c[e]]++;
                    q.push(e);
                } else if (c[e] == c[u]) {
                    cout << "Impossible" << endl;
                    return 0;
                }
            }
            q.pop();
        }
        cnt += min(f[1], f[0]);
    }
    cout << cnt << endl;
    return 0;
}

#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <queue>

using namespace std;

const int N = 11000, M = 110000;

queue<int> q;
int n, m, cnt, ans;
int c[N], f[2], s, head[N];

struct Edge {
    int to, pre;
} e[M * 2];
void inline addedge(Edge e[], int from, int to, int & cnt, int head[]) {
    e[cnt].to = to;
    e[cnt].pre = head[from];
    head[from] = cnt++;
}


void try_dfs(int x, int w) {
    c[x] = w;
    f[w]++;
    s++;
    for (int i = head[x], u; ~i; i = e[i].pre) {
        u = e[i].to;
        if (!~c[u]) {
            try_dfs(u, c[x] ^ 1);
        } else if (c[u] == w) {
            throw 1;
            return;
        }
    }
}

int main() {
    memset(head, -1, sizeof(head));
    memset(e, 0, sizeof(e));
    scanf("%d%d", &n, &m);
    for (int i = 0, q, r; i < m; i++) {
        scanf("%d%d", &q, &r);
        addedge(e, q, r, cnt, head);
        addedge(e, r, q, cnt, head);
    }
    memset(c, -1, sizeof(c));
    while (s != n) {
        f[0] = f[1] = 0;
        for (int i = 1; i <= n; i++) {
            if (!~c[i]) {
                try {
                    try_dfs(i, 0);
                } catch (...) {
                    cout << "Impossible" << endl;
                    return 0;
                }
                ans += min(f[1], f[0]);
                break;
            }
        }
    }
    cout << ans << endl;
    return 0;
}

本作品使用基于以下许可授权：Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License.