targan算法

blog:https://blog.csdn.net/Prediction__/article/details/100030166
视频:https://www.bilibili.com/video/BV1Q7411e7bM?p=2
例题:https://ac.nowcoder.com/acm/contest/7501/D
ac code:

代码块
//https://ac.nowcoder.com/acm/discuss/blogs?tagId=138773
#include <iostream>
#include <algorithm>
#include <stack>
using namespace std;
const int maxx = 3 * 1e5 + 50;
#define ll long long
ll read() {
    ll w = 1, x = 0; char c; c = getchar();
    while (!isdigit(c)) { if (c == '-') w = -1; c = getchar(); }
    while (isdigit(c)) { x = x * 10 + c - '0'; c = getchar(); }
    return w * x;
}
struct node {
    int to, nxt,val;
}edge[maxx * 2];
int cnt,head[maxx];
void addedge(int a, int b) {
    ++cnt;
    if (head[a]) {
        edge[cnt].nxt = head[a];
    }
    head[a] = cnt;
    edge[cnt].to = b;
}
int idx, dfn[maxx], low[maxx],num[maxx];
int base;
stack<int>st;
bool inst[maxx];
void targin(int n) {
    dfn[n] = low[n] = ++idx;
    ++num[n];
    st.push(n); inst[n] = 1;
    for (int i = head[n]; i != 0; i = edge[i].nxt) {
        int to = edge[i].to;
        if (to == 0) continue;
        if (!dfn[to]) {
            targin(to);
            low[n] = min(low[n], low[to]);
            num[n] += (low[to] >= dfn[n]);
        }
        else if(inst[to]){//说明在栈里面
            low[n] = min(low[n], dfn[to]);
        }
    }
    if (low[n] == dfn[n]) {//说明是根
         ++base;
        while (st.top() != n) {
            inst[st.top()] = 0;
            st.pop();
        }
        inst[st.top()] = 0;
        st.pop();
    }
}
int main() {
    int n, m,a,b; n = read(), m = read();
    for (int i = 0; i < m; i++) {
        a = read(), b = read(); addedge(a, b); addedge(b, a);
    }
    for (int i = 1; i <= n; i++) {
        if (!dfn[i]) targin(i), --num[i];;

    }
    for (int i = 1; i <= n; i++) {
        cout << base - 1 + num[i] << " ";
    }
    cout << endl;
}