Cod sursa(job #2858103)

Utilizator albertaizicAizic Albert albertaizic Data 26 februarie 2022 23:42:53
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.78 kb
#include <stdio.h>
#include <vector>
using namespace std;

#define MAX_N 100000

struct Node{
  int subset;
  vector<int> edges;
};

Node nodes[MAX_N];

void add(int a,int b){
  nodes[a].edges.push_back(b);
  nodes[b].edges.push_back(a);
}
void dfs(int nodeIndex,int subset){
  nodes[nodeIndex].subset=subset;

  for(int n : nodes[nodeIndex].edges)
    if(nodes[n].subset!=subset)
      dfs(n,subset);
}

int main(){
  FILE *fin,*fout;
  fin=fopen("dfs.in","r");
  fout=fopen("dfs.out","w");

  int n,m,i,a,b,nr;
  fscanf(fin,"%d%d",&n,&m);
  for(i=0;i<m;i++){
    fscanf(fin,"%d%d",&a,&b);
    add(a,b);
  }

  nr=0;
  for(i=1;i<=n;i++)
    if(nodes[i].subset==0)
      dfs(i,++nr);

  fprintf(fout,"%d",nr);
  fclose(fin);
  fclose(fout);
  return 0;
}