Cod sursa(job #2422109)

Utilizator tudose_bogdanTudose Bogdan tudose_bogdan Data 17 mai 2019 12:20:37
Problema Parcurgere DFS - componente conexe Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.63 kb
#include <iostream>
#include <vector>
#include <fstream>
using namespace std;

const int N = 100001;
vector<vector<int>> G(N);
int n, m;
ifstream f("dfs.in");
ofstream g("dfs.out");

void citire()
{
	f >> n >> m;
	for (int i = 0; i < m; i++)
	{
		int a, b;
		f >> a >> b;
		G[a].push_back(b);
		G[b].push_back(a);
	}
}
bool* viz = new bool[n];
void DFS(int sursa)
{
	viz[sursa] = 1;

	for (auto i : G[sursa])
	{
		if (!viz[i])
			DFS(i);
	}
}

int main()
{

	citire();

	int nrcomp = 0;
	
	for (int i = 1; i <= n; i++)
	{
		if (!viz[i])
		{
			nrcomp++;
			DFS(i);
		}
	}


	g << nrcomp;
	
}