#C240219A. 强连通分量

标签（Label）

• tarjan
• 模板

网址（Website）

$\qquad$USACO06JAN The Cow Prom S

代码（Code）

#include<bits/stdc++.h>
#include<vector>
#include<stack>
#define For(i,l,r) for(int i=l;i<=r;i++) 
#define Rof(i,l,r) for(int i=l;i>=r;i--)
using namespace std;
#define P pair<int,int>
#define int long long
inline int input(){int x;return cin>>x,x;}
const int inf = 0x3f3f3f3f3f3f3f3f;
const int N = 10123;

vector<int> ft[N];
stack<int> st;

int n,m,ans;

int dfn[N],low[N],t;
int scc[N],scc_cnt;
vector<int> strc[N];
void tarjan(int x){
	dfn[x]=low[x]=++t , st.emplace(x);
	for(auto y:ft[x]){
		if(!dfn[y])			tarjan(y) , low[x]=min(low[x],low[y]);
		else if(!scc[y])	low[x]=min(low[x],dfn[y]);
	}
	if(dfn[x]==low[x]){
		scc[x]=++scc_cnt;
		strc[scc_cnt].emplace_back(x);
		while(st.top()!=x){
			scc[st.top()]=scc_cnt;
			strc[scc_cnt].emplace_back(st.top());
			st.pop();
		}st.pop();
	}
}

signed main(){
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	int Tim = clock();
	cin>>n>>m;For(i,1,m){
		int x=input(),y=input();
		ft[x].emplace_back(y);
	}For(i,1,n) if(!dfn[i]) tarjan(i);
	For(i,1,scc_cnt) ans += strc[i].size()>1;
	cout<<ans<<'\n';
	return cerr<<"TIME:"<<(clock()-Tim)/1024.,0;
}