2020-2021 ICPC Northwestern European Regional Programming Contest (NWERC 2020) J Joint Excavation

题目描述

https://codeforces.com/gym/103049/problem/J

简要题意：给定一个 $n$ 个点 $m$ 条边的简单无向图，求是否存在一条链，使得将这条链上的点以及这些点的所有边都去掉后，剩下的点可以划分成两个集合，满足不同集合的点之间没有连边，链至少需要包含一个点，集合可以是空集

$n,m\le 2\times 10^5$

Solution

我们考虑一种神奇的 $dfs$ 的方法

一开始我们令所有点都属于集合 $A$，我们从任意一个点开始 $dfs$，每当我们 $dfs$ 到一个点，我们将就其从 $A$ 中删除，加入到我们所选择的这条链中，当我们回溯到某一个点的时候，我们将其从链中删除，加入到集合 $B$，显然集合 $A$ 和集合 $B$ 中的点之间不会存在连边，同时每次我们会将集合 $A$ 的大小减一或者将集合 $B$ 的大小加一，那么一定有存在一个时刻，满足 $A$ 的大小等于 $B$ 的大小

时间复杂度 $O(n)$

#include <iostream>
#include <algorithm>
#include <stack>
#include <vector>
#define maxn 200010
using namespace std;

int n, m;

struct Edge {
    int to, next;
} e[maxn * 2]; int c1, head[maxn];
inline void add_edge(int u, int v) {
    e[c1].to = v; e[c1].next = head[u]; head[u] = c1++;
}

int bl[maxn], cnt1, cnt2; stack<int> S;
void print() {
    cout << S.size() << " " << cnt1 << "\n";
    while (!S.empty()) {
        cout << S.top() << " "; S.pop();
    } cout << "\n"; vector<int> a1, a2; 
    for (int i = 1; i <= n; ++i)
        if (bl[i] == -1) a1.push_back(i);
        else if (bl[i] == 1) a2.push_back(i);
    for (auto t : a1) cout << t << " "; cout << "\n";
    for (auto t : a2) cout << t << " "; cout << "\n";
    exit(0);
}

bool vis[maxn];
void dfs(int u, int fa) {
    bl[u] = 0; S.push(u); if (--cnt1 == cnt2) print();
    vis[u] = 1; 
    for (int i = head[u]; ~i; i = e[i].next) {
        int v = e[i].to; if (v == fa || vis[v]) continue;
        dfs(v, u); 
    }
    bl[u] = -1; S.pop(); if (++cnt2 == cnt1) print();
}

int main() { fill(head, head + maxn, -1);
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    cin >> n >> m; cnt1 = n; cnt2 = 0;
    for (int i = 1; i <= n; ++i) bl[i] = 1; 
    for (int i = 1; i <= m; ++i) {
        int x, y; cin >> x >> y;
        add_edge(x, y); add_edge(y, x); 
    } dfs(1, 0); 
    return 0;
}