某島

… : "…アッカリ~ン . .. . " .. .
March 11, 2020

BZOJ 4316. 小C的獨立集

仙人掌圖最大獨立集。。。

const int N = int(5e4) + 9;
VI adj[N]; int fa[N];
int dfn[N], low[N], nn;
int f0[N], f1[N]; // 不取, 取 or 不取
int n, p;

void gao(int st, int ed) {
    int u,t,g0,g1;

    g0 = f0[st]; g1 = f0[st]; u = fa[st];
    while (u != ed) {
        int gg = g0;
        g0 = g1 + f0[u];
        g1 = gg + f1[u];
        checkMax(g1, g0);
        u = fa[u];
    }
    f1[u] += g0;

    g0 = f0[st]; g1 = f1[st]; u = fa[st];
    while (u != ed) {
        int gg = g0;
        g0 = g1 + f0[u];
        g1 = gg + f1[u];
        checkMax(g1, g0);
        u = fa[u];
    }
    checkMax(g1, g0);
    f0[u] += g1;
}

void dfs(int u = 0) {
#define v (*it)
    low[u] = dfn[u] = ++nn;

    ECH(it, adj[u]) if (v != fa[u]) {
        if (!dfn[v]) {
            fa[v] = u; dfs(v);
            checkMin(low[u], low[v]);
        } else {
            checkMin(low[u], dfn[v]);
        }
        if (dfn[u] < low[v]) {
            f0[u] += f1[v];
            f1[u] += f0[v];
        } else if (fa[v] != u && dfn[u] < dfn[v]) {
            gao(v, u);
        }
    }
    f1[u] += 1;
    checkMax(f1[u], f0[u]);
}

int main() {

#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
    //freopen("out.txt", "w", stdout);
#endif

    RD(n); Rush {
        int x, y; RD(x, y); --x, --y;
        adj[x].PB(y);
        adj[y].PB(x);
    }

    dfs();
    cout << f1[0] << endl;
}