Cod sursa(job #936705)

Utilizator s1mpMihai Alexandru s1mp Data 8 aprilie 2013 13:56:38
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.56 kb
#include<iostream>
#include<fstream>
#include<vector>
#define Nmax 100001
using namespace std;

vector <int> lista[Nmax];
int vizitat[Nmax];
int n,m,nr;

void DF(int k)
{vizitat[k]=1;
for(int i=0;i<lista[k].size();i++) if (!vizitat[lista[k][i]]) DF(lista[k][i]);}

int main()
{
	ifstream f("dfs.in");
	f>>n;
	f>>m;
	for(int i=0;i<m;i++)
		{int x,y;
		f>>x;
		f>>y;
		lista[x].push_back(y);
		lista[y].push_back(x);}
	for(int i=1;i<=n;i++)
		if(!vizitat[i]) {nr++;DF(i);}
	ofstream g("dfs.out");
		g<<nr;
f.close();
g.close();
return 0;
}