Cod sursa(job #1106704)

Utilizator crushackPopescu Silviu crushack Data 13 februarie 2014 04:20:28
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.43 kb
#include <stdio.h>
#include <algorithm>
#include <vector>
#include <stack>
#define NMax 100010

using namespace std;

const char IN[] = "ctc.in", OUT[] = "ctc.out";

int N, M;
vector<int> ad[NMax];
vector<vector<int> > Sol;

void tarjan( int x ) {

  static int low[NMax], idx[NMax], index;
  static bool b[NMax], inStack[NMax];
  static stack<int> St;
  static vector<int> vec;

  int i;

  if ( b[x] )
    return ;

  b[x] = true;
  inStack[x] = true;
  low[x] = idx[x] = ++ index;
  St.push(x);

  for ( i = 0; i < (int) ad[x].size(); ++ i) {

    if ( ! b[ ad[x][i] ] ) {
      tarjan( ad[x][i] );
      low[x] = min( low[x], low[ad[x][i]]);
    } else if ( inStack[ ad[x][i] ] )
      low[x] = min( low[x], low[ad[x][i]]);
  }

  if ( low[x] == idx[x] ) { // muhahahah
    vec.clear();
    do {
      i = St.top(); St.pop();
      vec.push_back(i);
      inStack[i] = false;
    } while ( i != x );
    Sol.push_back(vec);
  }

}

int main() {

  int i, j, x, y;
  freopen(IN, "r", stdin);
  scanf("%d%d", &N, &M);

  for ( i = 1; i <= M; ++ i) {
    scanf("%d %d", &x, &y);
    ad[x].push_back(y);
  }
  
  fclose ( stdin );

  for ( i = 1; i <= N; ++ i) tarjan( i );

  freopen( OUT, "w", stdout);
  printf("%d\n", (int) Sol.size() );
  for ( i = 0; i < (int) Sol.size(); ++ i) {
    sort( Sol[i].begin(), Sol[i].end() );
    for ( j = 0; j < (int) Sol[i].size(); ++ j) 
      printf("%d ", Sol[i][j]);
    printf("\n");
  }
  fclose(stdout);
  return 0;
}