80分玄关
查看原帖
80分玄关
1265349
HsNu1ly7_楼主2024/7/13 13:21

看了另一名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 ;
}

2024/7/13 13:21
加载中...