Cod sursa(job #633304)

Utilizator dany123Florea Daniel dany123 Data 13 noiembrie 2011 15:30:31
Problema Parcurgere DFS - componente conexe Scor 15
Compilator cpp Status done
Runda Arhiva educationala Marime 0.66 kb
//DFS recursiv cu STL
#include<iostream>
#include<fstream>
#include<vector>
using namespace std;
int n,m,viz[100001];
vector <int> v[100001];
void citire()
{
	ifstream fin("dfs.in");
	fin>>n>>m;
	int a,b;
	for (int i=0;i<m;i++)
	{
		fin>>a>>b;
		v[a].push_back(b);
	}
	fin.close();
}
void dfs (int nod)
{
	viz[nod]=1;
	for (int i=0;i<v[nod].size();i++) //pt fiecare vecin
		if (viz[v[nod][i]]==0) //daca e nevizitat
			dfs(v[nod][i]); //apelam dfs
}
int main ()
{
	citire();
	int nr=0;
	for (int i=1;i<=n;i++)
	{
		if (viz[i]==0)
		{
			dfs(i);
			nr++;
		}
	}
	
	ofstream fout("dfs.out");
	fout<<nr;
	fout.close();
	
	return 0;
}