Cod sursa(job #2423105)

Utilizator AlexNecula99Necula Florin-Alexandru AlexNecula99 Data 20 mai 2019 19:17:52
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.65 kb
#include <iostream>
#include <vector>
#include <fstream>

using namespace std;

int viz[100005];
vector <int> graph[100005];

void dfs(int node)
{
	viz[node] = 1;
	int lim = graph[node].size();
	for (int i = 0; i < lim; i++)
	{
		int vecin = graph[node][i];
		if (!viz[vecin])
			dfs(vecin);
	}
}

int main()
{
	ifstream f("dfs.in");
	ofstream g("dfs.out");
	int n, m;
	f >> n >> m;
	int a, b;
	for (int i = 1; i <= m; i++)
	{
		f >> a >> b;
		graph[b].push_back(a);
		graph[a].push_back(b);
	}
	int answer = 0;
	for (int i = 1; i <= n; i++)
	{
		if (!viz[i])
		{
			dfs(i);
			answer++;
		}
	}
	g << answer;
	return 0;
}