Cod sursa(job #403401)

Utilizator alex@ndraAlexandra alex@ndra Data 24 februarie 2010 22:00:20
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.16 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;
}