Cod sursa(job #3226070)

Utilizator RosheRadutu Robert Roshe Data 19 aprilie 2024 21:11:25
Problema Parcurgere DFS - componente conexe Scor 5
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.74 kb
#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];
  while(head){
    viz[head->nod] = 1;
    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);
  }
  
  int componente = 0;
  for(int i = 1; i<=N; i++){
    if(viz[i] == 1)
      continue;
    DFS(i); 
    componente++;
  }
  fout << componente;
}