Pagini recente » Cod sursa (job #862474) | Cod sursa (job #2081899) | Cod sursa (job #1918052) | Cod sursa (job #1124481) | Cod sursa (job #2551469)
#include <iostream>
#include <fstream>
using namespace std;
ifstream f("dfs.in");
ofstream f2("dfs.out");
int n, m, i;
int viz[100001];
struct Nod{
int info;
Nod *next;
};
Nod listaDeAdiacenta[100001];
void adaugare(Nod* prim, int y){
Nod* newNode = new Nod;
newNode->info = y;
newNode->next = NULL;
Nod* it = prim;
while(it->next != NULL) {
it = it->next;
}
it->next = newNode;
}
void dfs(int index_nod){
if(viz[index_nod] == 1) {
return;
}
viz[index_nod] = 1;
Nod * cap = listaDeAdiacenta[index_nod].next;
while(cap != NULL){
dfs(cap -> info);
cap = cap -> next;
}
}
int main()
{
int x, y;
int index_node;
f >> n >> m;
for(i = 1; i <= m; i++)
{
f >> x >> y;
Nod* listaX = &listaDeAdiacenta[x];
adaugare(listaX, y);
Nod* listaY = &listaDeAdiacenta[y];
adaugare(listaY, x);
}
for(i = 1; i <= n; i++){
viz[i] = 0;
}
int rez = 0;
for(i = 1; i <= n; i++){
if(viz[i] == 0){
dfs(i);
rez++;
}
}
f2 << rez;
return 0;
}