Cod sursa(job #2785833)

Utilizator Antonia_onisoruantonia onisoru Antonia_onisoru Data 19 octombrie 2021 17:09:28
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.23 kb
#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

ifstream in("dfs.in");
ofstream out("dfs.out");

const int MAXN = 100000;
int n;

struct nod{
  vector<int> next;
  bool vizitat;
};

nod noduri[MAXN + 1];

void read_graph(){
  int m, i, x, y;
  in>>n>>m;

  for( i = 0; i < m; i++ ){
    in>>x>>y;
    noduri[x].next.push_back(y);
    noduri[y].next.push_back(x);

  }

  /*for( i = 0; i < n; i++ ){
    out<<"numar nod: "<<i + 1<<" ";
    for( int j = 0; j < noduri[i].next.size(); j++ )
      out<<noduri[i].next[j] + 1<<" ";
    out<<'\n';
  }*/
}

void dfs(int index){

  noduri[index].vizitat = 1;
  //cout<<index + 1<<'\n';

  for(int i = 0; i < noduri[index].next.size(); i++ ){
    //cout<<noduri[noduri[index].next[i]].vizitat<<" "<<noduri[index].next[i] + 1<<" "<<noduri[noduri[index].next[i]].vizitat<<'\n';
    if( noduri[noduri[index].next[i]].vizitat == 0){
      dfs(noduri[index].next[i]);
    }
  }
}

int main()
{
    int cnt, i;
    read_graph();

    cnt = 0;
    for( i = 1; i <= n; i++ ){
      //cout<<noduri[i].vizitat<<'\n';
      if( noduri[i].vizitat == 0 ){
        cnt++;
        dfs(i);
      }
    }
    out<<cnt;
    return 0;
}