Cod sursa(job #406176)

Utilizator swxxIoo Andrei Rares swxx Data 1 martie 2010 12:02:29
Problema Componente tare conexe Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.01 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],y;
void citire()
{ 
	int i,x,j;
	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";
		
		g.close();
		return 0;
		}