全wa,样例过,求调
查看原帖
全wa,样例过,求调
1046030
Rainbow_rabbit楼主2024/2/28 18:26
#include <bits/stdc++.h>
using namespace std ;

int dfn[100004] , low[100004] , alow[100004] , n , m , t ;
vector <int> v[100004] ;
stack <int> s ;
bool f[100004] ;
bool ff[100004] ;

void dfs( int x )
{
	s.push(x) ;
	f[x] = 1 ;
	t ++ ;
	dfn[x] = t ;
	low[x] = t ;
	for( int y = 0 ; y < v[x].size() ; y ++ )
	{
		if( dfn[v[x][y]] == 0 ) 
		{
			dfs(v[x][y]) ;
			low[x] = min(low[x] , low[v[x][y]]) ;
		}
		else if( dfn[v[x][y]] != 0 && f[v[x][y]] == 1 )
		{
			low[x] = min(low[x] , low[v[x][y]]) ;
		}
	}
	if(dfn[x] == low[x])
	{
		f[s.top()] = 0 ;
		s.pop() ;
	}
}

int main()
{
	cin >> n >> m ;
	for( int i = 1 ; i <= m ; i ++ )
	{
		int u , uu ;
		cin >> u >> uu ;
		v[u].push_back(uu) ;
	}
	for( int i = 1 ; i <= n ; i ++ )
	{
		if( dfn[i] == 0 ) dfs(i) ;
	}
	int cnt = 0;
	for( int i = 1 ; i <= n ; i ++ )
	{
		if( !alow[low[i]] )
		{
			alow[low[i]] = 1 ;
			cnt ++ ;
		}
	}
	cout << cnt << endl ;
	for( int i = 1 ; i <= n ; i ++ )
	{
		int num = 0 ;
		if(ff[low[i]]) continue ;
		for( int j = 1 ; j <= n ; j ++ )
		{
			if( low[j] == low[i] ) 
			{
				cout << j << " " ;
			}
			ff[low[i]] = 1 ;
		}
		cout << endl ;
	}
	return 0 ;
}
2024/2/28 18:26
加载中...