Author: lllyouo
Date: 20250423
tag: tarjan、点双连通分量
link: https://www.acwing.com/problem/content/367/

问题描述

link

分析

略

参考代码

#include <bits/stdc++.h>
using namespace std;

const int N = 1010, M = 1e6 + 10;
int h[N], e[M * 2], ne[M * 2], idx;
int dfn[N], low[N], num, top, cnt;
int st[N], c[N], v[N], hate[N][N], able[N];
int n, m, root;
vector<int> dcc[N];

void add(int a, int b) {
    e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}

void tarjan(int x) {
    dfn[x] = low[x] = ++num;
    if (x == root && h[x] == 0) {
        dcc[++cnt].clear();
        dcc[cnt].push_back(x);
        return ;
    }
    st[++top] = x;
    for (int i = h[x]; i != -1; i = ne[i]) {
        int y = e[i];
        if (!dfn[y]) {
            tarjan(y);
            low[x] = min(low[x], low[y]);
            if (low[y] >= dfn[x]) {
                dcc[++cnt].clear();
                dcc[cnt].push_back(x);
                do {
                    dcc[cnt].push_back(st[top]);
                    top--;
                } while (st[top + 1] != y);
            }
        } else low[x] = min(low[x], dfn[y]);
    }
}

bool dfs(int x, int dcc_idx, int color) {
    v[x] = color;
    bool odd = false;
    for (int i = h[x]; i != -1; i = ne[i]) {
        int y = e[i];
        if (c[y] == dcc_idx) {
            if (!v[y]) odd |= dfs(y, dcc_idx, 3 - color);
            else if (v[y] != 3 - color) odd = true;
        }
    }
    return odd;
}

int main() {
    while (cin >> n >> m) {
        if (n == 0 && m == 0) break;
        memset(dfn, 0, sizeof dfn);
        memset(c, 0, sizeof c);
        memset(able, 0, sizeof able);
        memset(h, -1, sizeof h);
        idx = num = top = cnt = 0;
        
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                hate[i][j] = false;
            }
        }
        
        for (int i = 0; i < m; i++) {
            int a, b; scanf("%d%d", &a, &b);
            hate[a][b] = hate[b][a] = true;
        }
    
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                if (i != j && !hate[i][j]) add(i, j);
            }
        }
    
        for (int i = 1; i <= n; i++) {
            if (!dfn[i]) {
                root = i;
                tarjan(i);
            }
        }
        
        for (int i = 1; i <= cnt; i++) {
            for (int j = 0; j < dcc[i].size(); j++) {
                c[dcc[i][j]] = i;
                v[dcc[i][j]] = 0;
            }
            
            if(dfs(dcc[i][0], i, 1)) {
               for (int j = 0; j < dcc[i].size(); j++)
                    able[dcc[i][j]] = true;
            }
        }
        
        int ans = 0;
        for (int i = 1; i <= n; i++) {
            if (!able[i]) ans++;
        }
        cout << ans << endl;
    }
    
    return 0;
}