Luogu P6378 [PA2010]Riddle

题目描述

https://www.luogu.com.cn/problem/P6378

简要题意：给定一个 $n$ 个点 $m$ 条边的无向图，现在有已经将这 $n$ 个点分成了 $k$ 个集合，求是否可以在每个集合中恰好选一个关键点，且每条边至少有一个端点是关键点

$n,m\le 10^6$

Solution

我们考虑 $2-sat$，对于原图中的边的建图方法非常简单

注意到一个部分只能选恰好一个点，那么对于这个部分中的每个点 $u$

我们要建 $|S|$ 条边，分别是 $u\rightarrow v’,v\in S,v\neq u$

这样总共需要 $O(n^2)$ 条边，我们考虑搞一个前缀点和一个后缀点，这些点串联起来

那么只需要 $O(n)$ 条边，另外也可以直接用线段树优化建图，但注意到每个点要连的区间是一样的，所以没有必要使用线段树

#include <iostream>
#include <cstdio>
#include <stack>
#define maxn 4000010
using namespace std;

int n, m, k;

int a[maxn], pre[maxn], suf[maxn];

struct Edge {
    int to, next;
} e[8000010]; 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 dfn[maxn], low[maxn], c2, scc, id[maxn];
bool ins[maxn]; stack<int> S;
void tarjan(int u) {
    dfn[u] = low[u] = ++c2; ins[u] = 1; S.push(u);
    for (int i = head[u]; ~i; i = e[i].next) {
        int v = e[i].to;
        if (!dfn[v]) tarjan(v), low[u] = min(low[u], low[v]);
        else if (ins[v]) low[u] = min(low[u], dfn[v]);
    }
    if (low[u] == dfn[u]) {
        int t; ++scc;
        do {
            t = S.top(); S.pop();
            ins[t] = 0; id[t] = scc;
        } while (t != u); 
    }
}

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

    cin >> n >> m >> k;
    for (int i = 1; i <= m; ++i) {
        int x, y; cin >> x >> y;
        add_edge(x, y + n); add_edge(y, x + n); 
    } int cnt = 2 * n;
    for (int o = 1; o <= k; ++o) {
        int s; cin >> s;
        for (int i = 1; i <= s; ++i) cin >> a[i], pre[i] = ++cnt, suf[i] = ++cnt;
        for (int i = 1; i <= s; ++i) {
            add_edge(pre[i], a[i]); add_edge(suf[i], a[i]);
            if (i > 1) add_edge(a[i] + n, pre[i - 1]);
            if (i < s) add_edge(a[i] + n, suf[i + 1]); 
        }
        for (int i = 2; i <= s; ++i) add_edge(pre[i], pre[i - 1]);
        for (int i = s - 1; i; --i) add_edge(suf[i], suf[i + 1]); 
    }
    for (int i = 1; i <= cnt; ++i) if (!dfn[i]) tarjan(i);
    for (int i = 1; i <= n; ++i)
        if (id[i] == id[i + n]) return cout << "NIE\n", 0;
    cout << "TAK\n"; 
    return 0;
}