Cod sursa(job #1767306)

Utilizator potirasUAIC Borcan Andreea potiras Data 28 septembrie 2016 21:40:07
Problema Parcurgere DFS - componente conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.71 kb
// dfs-componente conxe.cpp : Defines the entry point for the console application.
//


#include<iostream>
#include<vector>
#include<fstream>
ifstream fin ("dfs.in");
ofstream fout ("dfs.out");
using namespace std;
int  ans, n, muc, i, j,ver[100000],a,b ;
vector <int> v[100000];
void dfs(int i)
{
	int j;

	for (j = 0; j != v[i].size(); j++)
	{
		if (ver[v[i][j]] == 0)
		{
			ver[v[i][j]] = 1;
			dfs(v[i][j]);
		}
	}
}


int main()
{
	fin >> n >> muc;
	for (i = 0; i < muc; i++)
	{
		fin >> a>>b;
		v[a].push_back(b);
		v[b].push_back(a);
	}
	for (i = 1; i <=n ; i++)
	{
		if (ver[i] == 0)
		{
			ver[i] = 1;
			dfs(i);
			ans++;
		}
	}
	fout << ans;
	
		return 0; 
}