Cod sursa(job #507747)

Utilizator Chip93Radu Ciprian Chip93 Data 6 decembrie 2010 18:07:36
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.57 kb
#include <fstream>
#include <vector>

using namespace std;

const int N = 100001;

vector<int> a[N];
int n;
bool viz[N];

ifstream in("dfs.in");
ofstream out("dfs.out");

void dfs(int x)
{
	int y;
	viz[x]=1;
	for(size_t i=0;i<a[x].size();i++)
	{
		y=a[x][i];
		if(!viz[y])
			dfs(y);
	}
}
int main()
{
	int m,x,y,d=0;
	in>>n>>m;
	while(m--)
	{
		in>>x>>y;
		a[x].push_back(y);//adaugi y in lista lui x
		a[y].push_back(x);
	}
	for(int i=1;i<=n;i++)
		viz[i]=0;
	for(int i=1;i<=n;i++)
		if(!viz[i])
		{
			d++;
			dfs(i);
		}
	out<<d;
}