Cod sursa(job #500517)

Utilizator adalLica Adela adal Data 12 noiembrie 2010 14:49:03
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.16 kb
#include <vector>
#include <stdio.h>
#include <string.h>
#define pb push_back 
using namespace std;

vector <int> L[100010], LT[100010];
bool sel[100010];
int st[100010], i, n, m, x, y, nr=0, nrc=0;

void dfs1(int x){
  vector <int>::iterator it;
  
  sel[x]=true;
  for (it=L[x].begin();it!=L[x].end();it++)
	  if (!sel[*it]) dfs1(*it);
  st[++nr]=x;

}

void dfs2(int x, bool ok){
  vector <int>::iterator it;
  
  sel[x]=true;
  if (ok) printf("%d ",x);
  for (it=LT[x].begin();it!=LT[x].end();it++)
	  if (!sel[*it]) dfs2(*it, ok);
  
}

void load(){
   scanf("%d %d\n", &n, &m);
   for (i=1; i<= m; i++){
   scanf("%d %d\n",&x, &y);
   L[x].pb(y);
   LT[y].pb(x);
  }
 return;
}

int main(){
 freopen("ctc.in","r",stdin);
 freopen("ctc.out","w",stdout);
 load();
 memset(sel, false, sizeof(sel));
 for (i=1; i<=n; i++)
   if (!sel[i])
	 dfs1(i);
 memset(sel, false, sizeof(sel));
 for (i=n; i>=1; i--)
   if (!sel[st[i]]){
	 nrc++; 
	 dfs2(st[i],false);
   }
 printf("%d\n", nrc);
 memset(sel, false, sizeof(sel));
 for (i=n; i>=1; i--)
   if (!sel[st[i]]){
	 dfs2(st[i],true);
	 printf("\n");
   }
  
return 0;
}