Cod sursa(job #2692168)

Utilizator NeoxDragos Stefan Neox Data 1 ianuarie 2021 13:36:35
Problema Parcurgere DFS - componente conexe Scor 15
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.66 kb
#include <fstream>
#include <queue>
using namespace std;

int main() {
	ifstream fin("dfs.in");
	ofstream fout("dfs.out");
	int n, m, conex = 0;
	fin >> n >> m;
	vector<vector<int>> adj(n + 1);
	vector<bool> vis(n + 1);
	queue<int> q;
	while(m--) {
		int x, y;
		fin >> x >> y;
		adj[x].push_back(y);
	}
	for(int k = 1; k <= n; k++) {
		if(!vis[k]) {
			conex++;
			vis[k] = 1;
			q.push(k);
			while(!q.empty()) {
				int nod = q.front();
				q.pop();
				vis[nod] = 1;
				for(int i : adj[nod]) {
					if(!vis[i]) {
						q.push(i);
						vis[i] = 1;
					}
				}
			}
		}
	}
	fout << conex;
	fin.close();
	fout.close();
	return 0;
}