Cod sursa(job #3226075)

Utilizator RosheRadutu Robert Roshe Data 19 aprilie 2024 21:32:38
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.83 kb
#include <iostream>
#include <vector>
#include <fstream>
#define SIZE 100010

using namespace std;

ifstream fin("dfs.in");
ofstream fout("dfs.out");
int viz[SIZE];

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;
}