Cod sursa(job #1088247)

Utilizator anaid96Nasue Diana anaid96 Data 20 ianuarie 2014 12:46:07
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.39 kb
#include<stdio.h>
#include<vector>

using namespace std;

FILE *in,*out;

//definitii
#define pb push_back

//constante
const int Nmax=(int)1e5+1;

//functii
void dfs(int nod);
void dfst(int nod);

//variabile
int n,m;
int nod1,nod2,nr,rez;
int postordine[Nmax];

vector<int>graf[Nmax];
vector<int>transpus[Nmax];
vector<int>answer[Nmax];

bool viz[Nmax];

int main(void)
{
	in=fopen("ctc.in","rt");
	fscanf(in,"%d%d",&n,&m);
	for(int i=1;i<=m;++i)
	{
		fscanf(in,"%d%d",&nod1,&nod2);
		graf[nod1].pb(nod2);
		transpus[nod2].pb(nod1);
	}	
	fclose(in);
	for(int i=1;i<=n;++i)
		if(!viz[i])
			dfs(i);
	for(int i=n;i>=1;--i)
		if(viz[postordine[i]])
		{	
			dfst(postordine[i]);
			rez++;
		}	
		
	out=fopen("ctc.out","wt");
	fprintf(out,"%d\n",rez);
	for(int i=0;i<=rez;++i)
	{
		vector<int>::iterator it,end=answer[i].end();
		for(it=answer[i].begin() ; it!=end ; ++it) 
			fprintf(out,"%d ",*it);
		fprintf(out,"\n");
	}	
	
	fclose(out);
	return 0;
}	

void dfs(int nod)
{
	viz[nod]=true;
	
	vector<int>::iterator it,end=graf[nod].end();
	for(it=graf[nod].begin() ; it!=end ; ++it)
		if(!viz[*it])
			dfs(*it);
	postordine[++nr]=nod;	
}	

void dfst(int nod)
{
	viz[nod]=false;
	answer[rez].pb(nod);
	vector<int>::iterator it,end=transpus[nod].end();
	for(it=transpus[nod].begin() ; it!=end ; ++it)
		if(viz[*it])
			dfst(*it);
		
		
}