Cod sursa(job #3158427)

Utilizator Dragos13Dragos Dragos13 Data 18 octombrie 2023 18:40:08
Problema Parcurgere DFS - componente conexe Scor 50
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.87 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
ifstream in("dfs.in");
ofstream out("dfs.out");
void construire(vector<vector<int>>&ls, int n, int m) {
	int x, y;
	for (int i = 0; i < m; i++)
	{
		in >> x >> y;
		ls[x].push_back(y);
		ls[y].push_back(x);
	}
}

int timp = 0;
int viz[100000],desc[100000],fin[100000],d[100000];
void dfs(vector<vector<int>>ls,int s) {
	viz[s] = 1;
	
	timp++;
	desc[s] = timp;
	for (int x : ls[s]) {
		if (viz[x] == 0) {
			d[x] = d[s] + 1;
			viz[x] = 1;
			dfs(ls,x);
		}
		
	}
	timp++;
	fin[s] = timp;

}


int main() {
	int n, m;
	in >> n >> m;
	int contor = 0;
	vector<vector<int>>ls(n + 1);
	construire(ls, n, m);
	
	for (int i = 1; i <=n; i++)
	{
		if (viz[i] == 0)
		{
			dfs(ls, i);
			contor++;
		}
	}
	out << contor;
	return 0;
}