Cod sursa(job #1972294)

Utilizator Robert29FMI Tilica Robert Robert29 Data 22 aprilie 2017 18:58:05
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.77 kb
#include<fstream>
#include<vector>
using namespace std;
ifstream cin("dfs.in");
ofstream cout("dfs.out");

void DFS(vector<int> *v, bool *viewed, int node)
{
	viewed[node] = true;

	for(int i = 0; i < v[node].size(); ++i)
	{
		int neighbour = v[node][i];
		if(!viewed[neighbour])
		{
			DFS(v, viewed, neighbour);
		}
	}
}

int main(){
	int n, m;
	cin >> n >> m;
	vector<int> v[n + 1];
	for(int i = 1; i <= m; ++i)
	{
		int x, y;
		cin >> x >> y;
		v[x].push_back(y);
		v[y].push_back(x);
	}

	bool viewed[n + 1];
	for(int i = 1; i <= n; ++i)
	{
		viewed[i] = false;
	}

	int nr = 0;
	for(int i = 1; i <= n; ++i)
	{
		if(!viewed[i])
		{
			++nr;
			DFS(v, viewed, i);
		}
	}

	cout << nr;

	cin.close();
	cout.close();
	return 0;
}