Cod sursa(job #1767311)

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


#include<iostream>
#include<vector>
#include<fstream>
using namespace std; using namespace std;
ifstream fin ("dfs.in");
ofstream fout ("dfs.out");

int  ans, n, muc, i, j,ver[100002],a,b ;
vector <int> v[100002];
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; 
}