Cod sursa(job #502580)

Utilizator George25Raduta George Cristian George25 Data 20 noiembrie 2010 10:02:18
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.23 kb
#include<stdio.h>
#include<string.h>
#include<vector>
using namespace std;

vector <int> l[100002], lt[100002];
bool sel[100002];
int st[100002],n=0,x,y,m,i,nr,nrc;

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

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);
}


int main(){
	freopen("ctc.in","r",stdin);
	freopen("ctc.out","w",stdout);
	load();
	/*scanf("%d%d",&n,&m);
	nrc=0;
	for (i=1; i<=m; i++){
		scanf("%d%d",&x,&y);
		l[x].push_back(y);
		lt[x].push_back(x);
	}*/
	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);
}