Cod sursa(job #2854544)

Utilizator iraresmihaiiordache rares mihai iraresmihai Data 21 februarie 2022 14:53:12
Problema Parcurgere DFS - componente conexe Scor 30
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.92 kb
#include <iostream>
#include <vector>

#define MAXN 100000

using namespace std;

struct node{
  vector <int> edges;
  bool visited;
};

node graph[MAXN];

static inline void addEdge(int a, int b) {
  graph[a].edges.push_back(b);
  graph[b].edges.push_back(a);
}

void dfs(int pos) {
  int i;

  graph[pos].visited = true;

  for ( i = 0; i < graph[pos].edges.size(); i++ )
    if ( !graph[graph[pos].edges[i]].visited )
      dfs(graph[pos].edges[i]);
}

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

  int n, m, a, b, ans, i;

  fscanf(fin, "%d%d", &n, &m);

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

  ans = 0;

  for ( i = 0; i < n; i++ ) {
    if ( !graph[i].visited ) {
      ans++;
      dfs(i);
    }
  }

  fprintf(fout, "%d\n", ans);

  fclose(fin);
  fclose(fout);
  return 0;
}