Cod sursa(job #1010217)

Utilizator crushackPopescu Silviu crushack Data 14 octombrie 2013 15:49:45
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.33 kb
#include <stdio.h>
#include <vector>
#include <stack>
#include <algorithm>
#define NMax 100010
using namespace std;

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

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

void tarjan(int x) {

  static int index = 0;
  static vector<int> aux;
  static stack<int> S;
  static bool inSt[NMax];

  if ( idx[x] ) return;
  
  S.push(x);
  idx[x] = low[x] = ++ index;
  inSt[x] = true;

  for (int i = 0 ; i < (int) ad[x].size(); ++ i)
    if ( !idx[ad[x][i]] ) {
      tarjan(ad[x][i]);
      low[x] = min( low[x], low[ ad[x][i] ] );
    } else if ( inSt[ad[x][i]] )
      low[x] = min( low[x], low[ ad[x][i] ] );

  if (idx[x] == low[x]) {
    int i; aux.clear();
    do {
      i = S.top(); S.pop();
      inSt[i] = false;
      aux.push_back(i);
    } while ( i != x );
    Sol.push_back(aux);
  }

}

int main() {

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

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

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