Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <cstdio>
- #include <cstring>
- #include <vector>
- #include <algorithm>
- using namespace std;
- #define MAXN 5005
- int N, M;
- int a, b;
- int f[ MAXN ];
- int dis[ MAXN ];
- int dad[ MAXN ];
- int sdom[ MAXN ];
- int idom[ MAXN ];
- int lazy[ MAXN ];
- int tree[ MAXN ];
- int best[ MAXN ];
- int path[ MAXN ];
- vector< int > G[ MAXN ];
- vector< int > g[ MAXN ];
- vector< int > bucket[ MAXN ];
- vector< int > Sol;
- int tick;
- void dfs( int n ) {
- dis[ n ] = ++tick;
- for( int i = 0; i < G[n].size(); ++i ) {
- if( dis[ G[n][i] ] ) continue;
- dad[ G[n][i] ] = n;
- dfs( G[n][i] );
- }
- }
- inline bool cmpf( int a, int b ) { return dis[a] < dis[b]; }
- inline int query( int n ) {
- if( tree[n] == 0 ) return -1;
- int pcnt = 0;
- for( int i = n; tree[i] != 0; i = tree[i] )
- path[ pcnt++ ] = i;
- for( int i = pcnt-2; i >= 0; --i ) {
- tree[ path[i] ] = tree[ path[ pcnt-1 ] ];
- int curr = path[i];
- int prev = path[i+1];
- if( dis[ sdom[ best[ curr ] ] ] > dis[ sdom[ best[ prev ] ] ] )
- best[ curr ] = best[ prev ];
- }
- return best[ n ];
- }
- inline int update( int d, int n ) {
- tree[n] = d; best[n] = n;
- }
- int main( void )
- {
- for( int tc = 0; tc < 10; ++tc ) {
- scanf( "%d%d", &N, &M );
- for( int i = 1; i <= N; ++i ) {
- G[ i ].clear();
- g[ i ].clear();
- bucket[ i ].clear();
- tree[ i ] = 0;
- lazy[ i ] = 0;
- dis[ i ] = 0;
- }
- for( int i = 0; i < M; ++i ) {
- scanf( "%d%d", &a, &b );
- G[ a ].push_back( b );
- g[ b ].push_back( a );
- }
- tick = 0;
- dfs( 1 );
- for( int i = 0; i < N; ++i ) f[i] = i+1;
- sort( f, f + N, cmpf );
- for( int i = N-1; i > 0; --i ) {
- int c = f[i];
- sdom[c] = c;
- for( int j = 0; j < g[c].size(); ++j ) {
- if( dis[ g[c][j] ] < dis[ sdom[c] ] ) sdom[c] = g[c][j];
- else {
- int d = query( g[c][j] );
- if( d == -1 ) continue;
- if( dis[ sdom[d] ] < dis[ sdom[c] ] ) sdom[c] = sdom[d];
- }
- }
- bucket[ sdom[c] ].push_back( c );
- update( dad[c], c );
- for( int j = 0; j < bucket[dad[c]].size(); ++j ) {
- int x = bucket[dad[c]][j];
- int d = query( x );
- if( d == -1 ) continue;
- if( sdom[x] == sdom[d] ) idom[x] = sdom[x];
- else lazy[x] = d;
- }
- bucket[dad[c]].clear();
- }
- Sol.clear();
- for( int i = 1; i < N; ++i ) {
- if( lazy[f[i]] != 0 ) idom[f[i]] = idom[lazy[f[i]]];
- Sol.push_back( idom[f[i]] );
- }
- sort( Sol.begin(), Sol.end() );
- Sol.resize( unique( Sol.begin(), Sol.end() )-Sol.begin() );
- printf( "%d\n", Sol.size() );
- for( int i = 0; i < Sol.size(); ++i )
- printf( "%d ", Sol[i] );
- putchar( '\n' );
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement