Cod sursa(job #797801)

Utilizator shuleavSulea Vlad shuleav Data 14 octombrie 2012 21:46:19
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.57 kb
#include <fstream>
#include <vector>
#define NM 100005
using namespace std;
ifstream f("dfs.in");
ofstream g("dfs.out");

vector <int> G[NM];
bool V[NM];
int i,n,m,x,y,nrc;

void DFS(int nod)
{
	int vec,i;
	V[nod]=1;
	for(i=0;i<G[nod].size();i++)
		{
			vec=G[nod][i];
			if(V[vec]==0)
				DFS(vec);
		}
}
int main()
{
    f >> n >> m;
    for(i=1;i<=m;i++)
    {
		f >> x >> y;
		G[x].push_back(y);
		G[y].push_back(x);
    }
    for(i=1;i<=n;i++)
		if(V[i]==0)
			nrc++,DFS(i);
	g << nrc << '\n';

	f.close();
	g.close();
    return 0;
}