Pagini recente » Cod sursa (job #1373976) | Cod sursa (job #1325948) | Cod sursa (job #2524096) | Cod sursa (job #1210825) | Cod sursa (job #3226074)
#include <iostream>
#include <vector>
#include <fstream>
#define SIZE 100000
using namespace std;
ifstream fin("dfs.in");
ofstream fout("dfs.out");
int viz[100000];
struct node{
int nod;
node* prev;
};
node* vertex[SIZE];
void add(node** head, int neighbor){
node *x = (node*)malloc(sizeof(node));
x->nod = neighbor;
x->prev = *head;
*head = x;
}
void DFS(int x){
node* head = vertex[x];
viz[x] = 1;
while(head){
if(viz[head->nod] == 0 && vertex[head->nod] != NULL){
DFS(head->nod);
}
head = head->prev;
}
}
int N, M;
int main(){
fin >> N >> M;
for(int i = 0; i<M; i++){
int x, y;
fin >> x >> y;
add(&vertex[x], y);
add(&vertex[y], x);
}
int componente = 0;
for(int i = 1; i<=N; i++){
if(viz[i] == 1)
continue;
DFS(i);
componente++;
}
fout << componente;
}