Cod sursa(job #597406)

Utilizator Smaug-Andrei C. Smaug- Data 22 iunie 2011 00:55:51
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.08 kb
#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;

#define MAXN 100005

vector<int> G[MAXN], R[MAXN];
int idx, I[MAXN], ll[MAXN], use[MAXN], S[MAXN], q, rq;

void tarjan(int n){
  
  I[n]=ll[n]=idx++;
  S[++q]=n; use[n]=1;

  vector<int>::iterator i;
  for(i=G[n].begin(); i != G[n].end(); i++){
    if(!I[*i]){
      tarjan(*i);
      ll[n]=min(ll[n], ll[*i]);
    }
    else if(use[*i])
      ll[n]=min(ll[n], ll[*i]);
  }
  if(I[n] == ll[n]){
    rq++;
    do {
      R[rq].push_back(S[q]);
      use[S[q]]=0; q--;
    } while(S[q+1] != n);
  }
}    

int main(){

  freopen("ctc.in", "r", stdin);
  freopen("ctc.out", "w", stdout);

  int N, M, i, a, b;
  vector<int>::iterator ii;

  scanf("%d%d", &N, &M);
  for(i=1; i<=M; i++){
    scanf("%d%d", &a, &b);
    G[a].push_back(b);
  }

  idx=1; q=0; rq=0;
  memset(I, 0, sizeof(I));
  memset(use, 0, sizeof(use));

  for(i=1; i<=N; i++)
    if(!I[i])
      tarjan(i);

  printf("%d\n", rq);
  for(i=1; i<=rq; i++){
    for(ii=R[i].begin(); ii != R[i].end(); ii++)
      printf("%d ", *ii);
    printf("\n");
  }

  return 0;

}