Advertisement
Guest User

Untitled

a guest
Jun 24th, 2017
53
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.11 KB | None | 0 0
  1. #include <cstdio>
  2. #include <cstring>
  3.  
  4. #include <vector>
  5. #include <algorithm>
  6.  
  7. using namespace std;
  8.  
  9. #define MAXN 5005
  10.  
  11. int N, M;
  12. int a, b;
  13.  
  14. int f[ MAXN ];
  15. int dis[ MAXN ];
  16. int dad[ MAXN ];
  17.  
  18. int sdom[ MAXN ];
  19. int idom[ MAXN ];
  20. int lazy[ MAXN ];
  21.  
  22. int tree[ MAXN ];
  23. int best[ MAXN ];
  24. int path[ MAXN ];
  25.  
  26. vector< int > G[ MAXN ];
  27. vector< int > g[ MAXN ];
  28. vector< int > bucket[ MAXN ];
  29. vector< int > Sol;
  30.  
  31. int tick;
  32.  
  33. void dfs( int n ) {
  34.    dis[ n ] = ++tick;
  35.    for( int i = 0; i < G[n].size(); ++i ) {
  36.       if( dis[ G[n][i] ] ) continue;
  37.       dad[ G[n][i] ] = n;
  38.       dfs( G[n][i] );
  39.    }
  40. }
  41.  
  42. inline bool cmpf( int a, int b ) { return dis[a] < dis[b]; }
  43.  
  44. inline int query( int n ) {
  45.    if( tree[n] == 0 ) return -1;
  46.    int pcnt = 0;
  47.    for( int i = n; tree[i] != 0; i = tree[i] )
  48.       path[ pcnt++ ] = i;
  49.      
  50.    for( int i = pcnt-2; i >= 0; --i ) {
  51.       tree[ path[i] ] = tree[ path[ pcnt-1 ] ];
  52.       int curr = path[i];
  53.       int prev = path[i+1];
  54.       if( dis[ sdom[ best[ curr ] ] ] > dis[ sdom[ best[ prev ] ] ] )
  55.          best[ curr ] = best[ prev ];
  56.    }
  57.    
  58.    return best[ n ];
  59. }
  60.  
  61. inline int update( int d, int n ) {
  62.    tree[n] = d; best[n] = n;
  63. }
  64.  
  65. int main( void )
  66. {
  67.    for( int tc = 0; tc < 10; ++tc ) {
  68.       scanf( "%d%d", &N, &M );
  69.      
  70.       for( int i = 1; i <= N; ++i ) {
  71.          G[ i ].clear();
  72.          g[ i ].clear();
  73.          bucket[ i ].clear();
  74.          tree[ i ] = 0;
  75.          lazy[ i ] = 0;
  76.          dis[ i ] = 0;
  77.       }
  78.      
  79.       for( int i = 0; i < M; ++i ) {
  80.          scanf( "%d%d", &a, &b );
  81.          G[ a ].push_back( b );
  82.          g[ b ].push_back( a );
  83.       }
  84.      
  85.       tick = 0;
  86.       dfs( 1 );
  87.      
  88.       for( int i = 0; i < N; ++i ) f[i] = i+1;
  89.       sort( f, f + N, cmpf );
  90.      
  91.       for( int i = N-1; i > 0; --i ) {
  92.          int c = f[i];
  93.          
  94.          sdom[c] = c;
  95.          
  96.          for( int j = 0; j < g[c].size(); ++j ) {
  97.             if( dis[ g[c][j] ] < dis[ sdom[c] ] ) sdom[c] = g[c][j];
  98.             else {
  99.                int d = query( g[c][j] );
  100.                if( d == -1 ) continue;
  101.                if( dis[ sdom[d] ] < dis[ sdom[c] ] ) sdom[c] = sdom[d];
  102.             }  
  103.          }
  104.          
  105.          bucket[ sdom[c] ].push_back( c );
  106.          update( dad[c], c );
  107.          
  108.          for( int j = 0; j < bucket[dad[c]].size(); ++j ) {
  109.             int x = bucket[dad[c]][j];
  110.             int d = query( x );
  111.             if( d == -1 ) continue;
  112.            
  113.             if( sdom[x] == sdom[d] ) idom[x] = sdom[x];
  114.             else lazy[x] = d;
  115.          }
  116.          
  117.          bucket[dad[c]].clear();
  118.       }
  119.      
  120.       Sol.clear();
  121.      
  122.       for( int i = 1; i < N; ++i ) {
  123.          if( lazy[f[i]] != 0 ) idom[f[i]] = idom[lazy[f[i]]];
  124.          Sol.push_back( idom[f[i]] );
  125.       }
  126.      
  127.       sort( Sol.begin(), Sol.end() );
  128.       Sol.resize( unique( Sol.begin(), Sol.end() )-Sol.begin() );
  129.      
  130.       printf( "%d\n", Sol.size() );
  131.      
  132.       for( int i = 0; i < Sol.size(); ++i )
  133.          printf( "%d ", Sol[i] );
  134.          
  135.       putchar( '\n' );
  136.    }
  137.    
  138.    return 0;
  139. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement