Cod sursa(job #2422108)

Utilizator tudose_bogdanTudose Bogdan tudose_bogdan Data 17 mai 2019 12:18:34
Problema Parcurgere DFS - componente conexe Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.64 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 = 1;
	DFS(1);
	for (int i = 2; i <= n; i++)
	{
		if (!viz[i])
		{
			nrcomp++;
			DFS(i);
		}
	}


	g << nrcomp;
	
}