Cod sursa(job #758595)

Utilizator VisuianMihaiMihai Visuian VisuianMihai Data 16 iunie 2012 09:09:32
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.66 kb
#include<fstream>
#include<vector>
using namespace std;
ifstream fin("dfs.in");
ofstream fout("dfs.out");
vector<int> v[200001];
bool visited[100001];
void dfs(int x)
{
	for ( int i = 0; i < v[x].size(); i++ )
	{
		if ( !visited[v[x][i]] )
		{
			visited[v[x][i]] = true;
			dfs(v[x][i]);
		}
	}
}
int main()
{
	int n, k, x, y, i, components = 0;
	fin >> n >> k;
	for ( i = 1; i <= k; i++ )
	{
		fin >> x >> y;
		v[x].push_back(y);
		v[y].push_back(x);
	}
	for ( i = 1; i <= n; i++ )
	{
		if ( !visited[i] )
		{
			components++;
			visited[i] = true;
			dfs(i);
		}
	}
	fout << components;
	fin.close();
	fout.close();
	return 0;
}