Cod sursa(job #748923)

Utilizator stanescu_teodorStanescu Teodor stanescu_teodor Data 15 mai 2012 10:06:53
Problema Parcurgere DFS - componente conexe Scor 80
Compilator cpp Status done
Runda Arhiva educationala Marime 0.64 kb
#define pb push_back
#include <algorithm>
#include <vector>
#include <fstream>
using namespace std;

vector <int> g1[100000];
vector <int> :: iterator it;
int n,m,i,x,y,nc;
bool sel[100000];
ifstream f ("dfs.in");
ofstream g ("dfs.out");

void dfs (int x)
{
	vector <int> :: iterator it;
	sel[x]=true;
	for (it=g1[x].begin(); it!=g1[x].end(); it++)
		if (!sel[*it])
		{
			sel[*it]=true;
			dfs(*it);
		}
}

int main ()
{
	f >>n>>m;
	for (i=1; i<=m; i++)
	{
		f>>x>>y;
		g1[x].pb(y);
		g1[y].pb(x);
	}
	nc=0;
	for (i=1; i<=n; i++)
		if (!sel[i]) 
		{
			nc++;
			dfs(i);
		}
	g<<nc;
	f.close();
	g.close();
}