Cod sursa(job #1082627)

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

using namespace std;

FILE *in,*out;

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

int n,m;
int nod1,nod2;
int postordine[Nmax];
int nrc,rez;
vector<int> answer[Nmax];
bool viz[Nmax];
vector<int> graf[Nmax],graft[Nmax];

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

int main(void)
{
	in=fopen("ctc.in","rt");
	fscanf(in,"%d%d",&n,&m);
	for(int i=0;i<m;++i)
	{
		fscanf(in,"%d%d",&nod1,&nod2);
		graf[nod1].push_back(nod2);
		graft[nod2].push_back(nod1);
	}	
	fclose(in);
	for(int i=1;i<=n;++i)
		if(!viz[i])
			dfs(i);
	for(int i=nrc;i>=0;--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[nrc++]=nod;
	
}

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