Cod sursa(job #406174)

Utilizator swxxIoo Andrei Rares swxx Data 1 martie 2010 12:00:46
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.07 kb
#include<fstream>
#include<vector>
using namespace std;
#define Nmax 100001
vector<int> G[Nmax],Gt[Nmax],Comp[Nmax];

int n,m,nrc,postordine[Nmax],nr, k,vizitat[Nmax];
void citire()
{
	int i,x,y;
	ifstream f("ctc.in");
	f>>n>>m;
	for(i=1;i<=m;i++)
	{
	f>>x>>y;
	G[x].push_back(y);
	Gt[y].push_back(x);
	}
	f.close();
}
void df(int nod)

{
int i,vecini;
vizitat[nod]=1;
vecini=G[nod].size();
for(i=0; i < vecini; i++)

	if (!vizitat[G[nod][i]])
	
		df(G[nod][i]);
		
	postordine[++nr]=nod;
}


void df2(int nod)
{
	int i,vecini;
	Comp[nrc].push_back(nod);
	vizitat[nod]=0;
	vecini=	Gt[nod].size();
	for(i=0;i<vecini;i++)
		if (vizitat[Gt[nod][i]])
			df2(Gt[nod][i]);
		
}

int main()
{
int i,vecini,j;
citire();
for(i=1;i<=n;i++)
	if (!vizitat[i])
		df(i);
	for(i=n;i>0;i--)
		
	if (vizitat[postordine[i]])
	{
	nrc++;
	k=0;
	df2(postordine[i]);
	}
	
	ofstream g("ctc.out");
	g<<nrc<<"\n";
	for(i=1;i<=nrc;i++)
	{
	vecini=Comp[i].size();
	for(j=0;j<vecini;j++)
		g<<Comp[i][j]<<"  ";
	g<<"\n";
	}
	
	g.close();
	return 0;
}