Cod sursa(job #2065802)

Utilizator bent_larsenSturzu Antonio-Gabriel bent_larsen Data 14 noiembrie 2017 11:10:00
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.79 kb
#include <fstream>
#include <vector>
#include <cstring>
using namespace std;

const int nmax = 100006;
bool viz[nmax];
vector<vector<int> > adj;

void dfs (int root)
{
	viz[root] = true;
	for(int i = 0;i < (int) adj[root].size();++i)
	{
		int nod = adj[root][i];
		if(!viz[nod])
		{
			dfs(nod);
		}
	}
}

int df (int N)
{
	int ans = 0;
	
	for(int i = 0;i < N;++i)
	{
		if(!viz[i])
		{
			dfs(i);
			++ans;
		}
	}
	return ans;
}

int main()
{
	int N, M;
	
	ifstream in("dfs.in");
	ofstream out("dfs.out");
	
	in >> N >> M;
	adj.resize(N);
	
	for(int i = 0;i < M;++i)
	{
		int a, b;
		in >> a >> b;
		--a, --b;
		adj[a].push_back(b);
		adj[b].push_back(a);
	}
	memset(viz, false, sizeof(viz));
	out<< df(N) << "\n";
	in.close();
	out.close();
}