tarjan算法写炸了,求助~
查看原帖
tarjan算法写炸了,求助~
848813
coding_bian楼主2025/1/18 15:25

救命48分求助

#include <bits/stdc++.h>
#define int long long
using namespace std;
int n, m;
vector<int> G[100005];
int dfn[100005], low[100005], co[100005], num[100005];
bool inst[100005];
int tot;
stack<int> st;
int cnt;
int du[100005];

void paint(int x) {
    st.pop();
    co[x] = cnt;
    num[cnt]++;
    inst[x] = 0;
}

void tarjan(int now) {
    dfn[now] = low[now] = ++tot;
    st.push(now);
    inst[now] = true;
    for(int i = 0; i < G[now].size(); i++) {
        int v = G[now][i];
        if(!dfn[v]) {
            tarjan(v);
            low[now] = min(low[v], low[now]);
        }else if(inst[v]) {
            low[now] = min(low[now], dfn[v]);
        }
    }
    if(low[now] == dfn[now]) {
        cnt++;
        while(st.top() != now) {
            int x = st.top();
            st.pop();
		    co[x] = cnt;
		    num[cnt]++;
		    inst[x] = 0;
        }
		st.pop();
	    co[now] = cnt;
	    num[cnt]++;
	    inst[now] = 0;
    }
}

signed main() {
    cin >> n >> m;
    for(int i = 0; i < m; i++) {
        int a, b;
        cin >> a >> b;
        G[a].push_back(b);
    }

    for(int i = 1; i <= n; i++) {
        if(!dfn[i]) {
            tarjan(i);
        }
    }

    for(int i = 1; i <= n; i++) {
        for(int j = 0; j < G[i].size(); j++) {
            int v = G[i][j];
            if(co[i] != co[v]) {
                du[co[v]]++;
            }
        }
    }

    int ans = 0;
    for(int i = 1; i <= cnt; i++) {
        if(du[i] == 0) {
            ans = num[i];
        }
    }

    cout << ans << endl;

    return 0;
}
2025/1/18 15:25
加载中...