Pagini recente » Soldati | Cod sursa (job #355141) | Cod sursa (job #1805197) | Cod sursa (job #993375) | Cod sursa (job #3275619)
#include <iostream>
#include <fstream>
#include <queue>
#include <bitset>
#include <vector>
#define maxSize 100001
using namespace std;
vector<vector<int>> readAdjacencyList(ifstream &fin, int nodes, int edges, bool isDirected = false) {
vector<vector<int>> adjList(nodes + 1);
for (int i = 0; i < edges; i++) {
int x, y;
fin >> x >> y;
adjList[x].push_back(y);
if (!isDirected) {
adjList[y].push_back(x);
}
}
return adjList;
}
bitset<maxSize> marked;
void depthFirstSearch(const vector<vector<int>>& adjList, int node) {
marked[node] = true;
for (auto neighbor : adjList[node]) {
if (!marked[neighbor]) {
depthFirstSearch(adjList, neighbor);
}
}
}
int main() {
ifstream fin("dfs.in");
ofstream fout("dfs.out");
int components = 0;
int nodes, edges;
fin >> nodes >> edges;
auto adjList = readAdjacencyList(fin, nodes, edges);
for (int i = 1; i <= nodes; i++) {
if (marked[i] == false) {
depthFirstSearch(adjList, i);
components++;
}
}
fout << components << endl;
fin.close();
fout.close();
return 0;
}