Pagini recente » Cod sursa (job #345985) | Cod sursa (job #2774574) | Cod sursa (job #1005081) | Cod sursa (job #2329526) | Cod sursa (job #3196639)
#include <iostream>
#include <fstream>
#include <vector>
#include <unordered_set>
using namespace std;
class Graph {
public:
int N; // Numărul de noduri
vector<vector<int>> adjacencyList;
Graph(int n) : N(n), adjacencyList(n) {}
void addEdge(int u, int v) {
adjacencyList[u].push_back(v);
adjacencyList[v].push_back(u);
}
};
void DFS(const Graph& graph, int node, unordered_set<int>& visited) {
visited.insert(node);
for (int neighbor : graph.adjacencyList[node]) {
if (visited.find(neighbor) == visited.end()) {
DFS(graph, neighbor, visited);
}
}
}
int numarComponenteConexe(const Graph& graph) {
unordered_set<int> visited;
int componenteConexe = 0;
for (int node = 0; node < graph.N; ++node) {
if (visited.find(node) == visited.end()) {
DFS(graph, node, visited);
componenteConexe++;
}
}
return componenteConexe;
}
int main() {
ifstream infile("dfs.in");
ofstream outfile("dfs.out");
if (!infile || !outfile) {
cerr << "Nu s-a putut deschide fisierul de intrare/iesire.\n";
return 1;
}
int N, M;
infile >> N >> M;
Graph graph(N);
// Citirea muchiilor
for (int i = 0; i < M; ++i) {
int X, Y;
infile >> X >> Y;
graph.addEdge(X - 1, Y - 1); // Graful este indexat de la 0
}
int rezultat = numarComponenteConexe(graph);
// Afisarea rezultatului in fisierul de iesire
outfile << rezultat << endl;
infile.close();
outfile.close();
return 0;
}