看了另一名dalao的提示,但我发现我好像并没有他说的那种错误,玄关。
#include <iostream>
#include <vector>
#include <stack>
using namespace std ;
#define int long long
vector <int> g[10010] ;
stack <int> stk ;
int n , m ;
int a , b ;
int dfn[10010] , low[10010] ;
int cnt = 0 ;
int instk[10010] ;
int siz[10010] ;
int tot;
int scc[10010] ;
int vis[10010] ;
void tarjan ( int now ){
dfn[now] = low[now] = (++cnt) ;
stk.push ( now ) ;
// vis[now] = 1 ;
instk[now] = 1 ;
for ( int i = 0 ; i < g[now].size() ; i++ ){
if ( instk[g[now][i]] == 0 ){
tarjan ( g[now][i] ) ;
low[now] = min ( low[now] , low[g[now][i]] ) ;
}else if ( instk[g[now][i]] == 1 ){
low[now] = min ( low[now] , dfn[g[now][i]] ) ;
}
}
if ( dfn[now] == low[now] ){
++tot ;
int temp ;
do{
temp = stk.top() ;
stk.pop() ;
instk[temp] = 0 ;
siz[tot]++ ;
scc[tot] = tot ;
}while ( now != temp ) ;
// while ( stk.top() != now ){
// int temp = stk.top() ;
// stk.pop() ;
// instk[temp] = 0 ;
// siz[tot]++ ;
// scc[tot] = temp ;
// }
// int t = stk.top() ;
// stk.pop() ;
// instk[t] = 0 ;
// siz[tot]++ ;
// scc[tot] = t ;
}
}
signed main (){
ios::sync_with_stdio(0) ;
cin.tie(0) ;
cout.tie(0) ;
cin >> n >> m ;
for ( int i = 1 ; i <= m ; i++ ){
int a , b ;
cin >> a >> b ;
g[a].push_back( b ) ;
}
for ( int i = 1; i <= n ; i++ ){
if ( dfn[i] == 0 ) tarjan(i) ;
}
int ans = 0 ;
for ( int i = 1 ; i <= tot ;i++ ){
if ( siz[i] > 1 ) ans++ ;
}
cout << ans ;
return 0 ;
}