Cod sursa(job #2710387)

Utilizator bubblegumixUdrea Robert bubblegumix Data 22 februarie 2021 15:32:54
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.7 kb
#include<iostream>
#include<vector>
#include<fstream>
#define NMAX 100005
using namespace std;
ifstream f("dfs.in");
ofstream g("dfs.out");

vector<int> graf[NMAX];
int n, m;

void read()
{
	f >> n >> m;
	for (int i = 1; i <= m; i++)
	{
		int x, y;
		f >> x >> y;
		graf[x].push_back(y);
		graf[y].push_back(x);
	}
}
void dfs(int source, vector<bool>& isUsed)
{
	isUsed[source] = true;
	for (auto it : graf[source])
		if (!isUsed[it])
			dfs(it, isUsed);

}
void solve()
{
	int nr = 0;
	vector<bool> isUsed(n+1, false);
	for (int i = 1; i <= n; i++)
		if (isUsed[i] == false)
		{
			dfs(i, isUsed);
			nr++;
		}
	g << nr;

}


int main()
{
	read();
	solve();
	return 0;
}