Cod sursa(job #1314815)

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

using namespace std;

FILE *in,*out;

//definitii
#define pb push_back

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

//variabile
int n,m;
int x,y;
int nr, rez;

int postordine[Nmax];

bool viz[Nmax];

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

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

int main(void)
{
	in = fopen("ctc.in","rt");
	out = fopen("ctc.out","wt");
		
	fscanf(in,"%d%d",&n, &m);
	
	for(int i=1; i<=m; ++i)
	{
		fscanf(in,"%d%d",&x,&y);
		graf[x].pb(y);
		graft[y].pb(x);
	}
	
	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++;
		}
	
	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(in);
	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 node)
{
	viz[node] = false;
	answer[rez].pb(node);
	
	vector<int> :: iterator it, end=graft[node].end();
	for(it = graft[node].begin(); it != end; ++it)
		if(viz[*it])
			dfst(*it);
}