Cod sursa(job #1077077)

Utilizator robert_stefanRobert Stefan robert_stefan Data 10 ianuarie 2014 21:11:24
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.58 kb
#include <fstream>
#include <vector>
#define IN "dfs.in"
#define OUT "dfs.out"
#define NMAX 100005

using namespace std;

ifstream in(IN);
ofstream out(OUT);

vector <int> G[NMAX];
int v[NMAX], n;

inline void DF(int nod, int c)
{
	int i;
	v[nod]=c;
	for(i=0; i<G[nod].size(); ++i)
		if(!v[G[nod][i]])
			DF(G[nod][i], c);
}

int main()
{
	int m, a, b, i, c=0;
	in>>n>>m;
	while(m)
	{
		in>>a>>b;
		G[a].push_back(b);
		G[b].push_back(a);
		--m;
	}
	for(i=1; i<=n; ++i)
		if(!v[i])
			DF(i, ++c);
	out<<c<<'\n';
	in.close();
	out.close();
	return 0;
}