Cod sursa(job #3295221)

Utilizator andrei17052004Andrei Alexandrescu andrei17052004 Data 3 mai 2025 17:29:43
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.69 kb
#include <bits/stdc++.h>
using namespace std;

void dfs(int node, vector<vector<int>>& adj, vector<int>& visited)
{
	for (int neigh : adj[node])
		if (!visited[neigh])
		{
			visited[neigh] = 1;
			dfs(neigh, adj, visited);
		}
}

int main()
{
	ifstream fin("dfs.in");
	ofstream fout("dfs.out");
	int n, m;
	fin >> n >> m;
	vector<vector<int>> adj(n + 1);
	int i, x, y;
	for (i = 0 ; i < m ; i++)
	{
		fin >> x >> y;
		adj[x].push_back(y);
		adj[y].push_back(x);	
	}
	vector<int> visited(n + 1, 0);
	int cnt = 0;
	for (i = 1 ; i <= n ; i++)
		if (!visited[i])
		{
			dfs(i, adj, visited);
			cnt++;
		}
	fout << cnt << endl;
	fin.close();
	fout.close();
	return 0;
}