Pagini recente » Cod sursa (job #3176796) | Cod sursa (job #1224266) | Cod sursa (job #3185726) | Cod sursa (job #2870551) | Cod sursa (job #3158291)
#include <iostream>
#include <fstream>
#include <vector>
#include <list>
#include <queue>
using namespace std;
ifstream fin("dfs.in");
ofstream fout("dfs.out");
void dfs(int node, vector <bool>& visited, vector<list<int>>& adjacencyList) {
visited[node] = true;
for (int neighbor : adjacencyList[node]) {
if (!visited[neighbor]) {
dfs(neighbor, visited, adjacencyList);
}
}
}
vector<list<int>> from_edges_to_list (int n, list<pair<int, int>> edges) {
vector<list<int>> adjacencyList;
adjacencyList.resize(n + 1);
for (auto p : edges) {
adjacencyList[p.first].push_back(p.second);
}
return adjacencyList;
}
int main() {
int N, M;
list <pair <int, int>> edges;
fin >> N >> M;
for (int i = 0; i < M; i++) {
int x, y;
fin >> x >> y;
edges.push_back(make_pair(x, y));
}
// creez lista de adiacenta
vector<list <int>> adjacencyList = from_edges_to_list(N, edges);
// vectorul in care verific daca un nod a fost vizitat
vector <bool> visited((N + 1), false);
int counter = 0; // nr componente conexe
// verific ce noduri au fost vizitate
for (int i = 1; i <= N; i++) {
// daca nodul i nu a fost vizitat, apelez dfs
// si adaug inca o componenta conexa
if (!visited[i]) {
dfs(i, visited, adjacencyList);
counter++;
}
}
fout << counter;
}