Cod sursa(job #2641726)

Utilizator richardionelRichard Ionel richardionel Data 12 august 2020 15:35:03
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.76 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <string>
using namespace std;

const string problem = "dfs";
ifstream fin(problem + ".in");
ofstream fout(problem + ".out");

#define ll long long
const ll mmax = 150005;

ll comp;
vector <int> nods[mmax];
bool is[mmax];
ll n,m;

void dfs(int start)
{
	is[start] = true;
	for (unsigned int i = 0; i < nods[start].size(); i++)
	{
		int vecin = nods[start][i];
		if (!is[vecin])
			dfs(vecin);
	}
}

int main()
{	
	fin >> n >> m;
	while (m--)
	{
		int nod1, nod2;
		fin >> nod1 >> nod2;
		nods[nod1].push_back(nod2);
		nods[nod2].push_back(nod1);
	}

	
	for (unsigned int i = 1; i <= n; i++)
	{	
		if (!is[i])
		{
			dfs(i);
			comp++;
		}
	}

	fout << comp;
}