tarjan算法(有向图，无向图)

P2863奶牛舞会(有向图): https://www.luogu.com.cn/problem/P2863

#include <iostream>
#include <vector>
#include <stack>

using namespace std;
vector<int> a[300000];
int low[300000], dfn[300000], cnt, nu, isHave[300000], tt;
bool ins[300000];
stack<int> s;

void sout(int ss) {
	isHave[tt]++;
	ins[ss] = 0;
	s.pop();
}

void dfs(int x, int fa) {
	s.push(x);
	ins[x] = 1;
    dfn[x] = ++nu;
    low[x] = nu;
    for (int to : a[x]) {
        if (!dfn[to]) {
	        dfs(to, x);
	        low[x] = min(low[x], low[to]);
        } else if(ins[to]) low[x] = min(low[x], dfn[to]);
    }
	
    if (dfn[x] == low[x]) {
    	tt++;
    	while (s.top() != x) {
    		sout(s.top());
		}
		sout(x);
		
	}
	
}


int main() {
     int m, n;
     cin >> n >> m;
     for (int i=1;i<=m;i++) {
         int x, y;
         cin >> x >> y;
         a[x].push_back(y);
     }
    for (int i=1;i<=n;i++) {
    	if (!dfn[i]) dfs(i, i);
    }
    for (int i=1;i<=n;i++) {
    	if (isHave[i] > 1) cnt++;
	}
    cout << cnt << endl;
    return 0;
}

未完待续