bzoj 4316 小C的独立集

题目描述

给定一个边仙人掌，$n$ 个点，$m$ 条边，求最大独立集

$n\le 50000,m\le 60000$

Solution

按照仙人掌 $dp$ 的套路，我们只需要考虑简单环的情况

在这道题中，我们只需要钦定简单环最低点选还是选，这样可以直接破环为链

#include <iostream>
#define maxn 50010
#define maxm 60010
#define INF 1000000000
using namespace std;

int n, m;

struct Edge {
    int to, next;
} e[maxm * 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 f[maxn][2], fa[maxn];
void dp(int u, int v) {
    int t = fa[v], fu[2], fv[2] = { f[v][0], f[v][1] };
    while (t != u) {
        fu[0] = max(fv[0], fv[1]) + f[t][0];
        fu[1] = fv[0] + f[t][1];
        swap(fu, fv); t = fa[t];
    }
    f[u][0] += max(fv[0], fv[1]);
    
    fv[0] = f[v][0]; fv[1] = -INF; t = fa[v]; 
    while (t != u) {
        fu[0] = max(fv[0], fv[1]) + f[t][0];
        fu[1] = fv[0] + f[t][1];
        swap(fu, fv); t = fa[t];
    }
    f[u][1] += fv[0];
}

int dfn[maxn], low[maxn];
void dfs(int u) {
    static int cnt = 0;
    dfn[u] = low[u] = ++cnt;
    f[u][0] = 0; f[u][1] = 1; 
    for (int i = head[u]; ~i; i = e[i].next) {
        int v = e[i].to; if (v == fa[u]) continue;
        if (!dfn[v]) {
            fa[v] = u; dfs(v);
            low[u] = min(low[u], low[v]); 
        }
        else low[u] = min(low[u], dfn[v]);
        if (low[v] > dfn[u]) {
            f[u][0] += max(f[v][0], f[v][1]);
            f[u][1] += f[v][0];
        }
    }
    for (int i = head[u]; ~i; i = e[i].next) {
        int v = e[i].to; if (u == fa[v] || dfn[v] < dfn[u]) continue;
        dp(u, v); 
    }
}

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

    cin >> n >> m;
    for (int i = 1; i <= m; ++i) {
        int x, y; cin >> x >> y;
        add_edge(x, y); add_edge(y, x);
    } dfs(1); cout << max(f[1][0], f[1][1]) << "\n";
    return 0;
}