Pagini recente » Cod sursa (job #714586) | Cod sursa (job #2896777) | Cod sursa (job #845704) | Cod sursa (job #2700220) | Cod sursa (job #2641899)
#include <iostream>
#include <fstream>
const int Nodes = 100005;
bool Visited[Nodes];
int count;
struct Node {
int index;
struct Node* next;
};
struct Node* N[Nodes];
void addAdjacentNode(Node*& header, int i) {
Node* iterator = header;
while (iterator->next != NULL)
iterator = iterator->next;
Node* added = new Node;
added->index = i;
added->next = NULL;
iterator->next = added;
return;
}
void DFS(int index) {
if (Visited[index]) return;
Visited[index] = true;
Node* iterator = N[index];
while (iterator->next != NULL) {
iterator = iterator->next;
DFS(iterator->index);
}
return;
}
int main() {
std::ifstream fin("dfs.in");
std::ofstream fout("dfs.out");
int nodes{}, edges{}, i{};
fin >> nodes >> edges;
for (i = 1; i <= nodes; i++) {
N[i] = new Node;
N[i]->index = i;
N[i]->next = NULL;
}
while (edges--) {
int x{}, y{};
fin >> x >> y;
addAdjacentNode(N[x], y);
addAdjacentNode(N[y], x);
}
for (i = 1; i <= nodes; i++) {
if (!Visited[i]) {
DFS(i);
count++;
}
}
fout << count << "\n";
fin.close();
fout.close();
return 0;
}