Cod sursa(job #3158417)

Utilizator Dragos13Dragos Dragos13 Data 18 octombrie 2023 18:25:18
Problema Parcurgere DFS - componente conexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.05 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
ifstream in("dfs.in");
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);
	}
}
void afisare(vector<vector<int>>ls)
{
	for (int i = 1; i < ls.size(); i++)
	{
		cout << i << ": ";
		for (int j = 0; j < ls[i].size(); j++)
		{
			cout << ls[i][j] << " ";
		}cout << "\n";
	}
}
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);
	afisare(ls);
	for (int i = 1; i <=n; i++)
	{
		if (viz[i] == 0)
		{
			dfs(ls, i);
			contor++;
		}
	}
	cout << contor;
	return 0;
}