Cod sursa(job #2785825)

Utilizator Antonia_onisoruantonia onisoru Antonia_onisoru Data 19 octombrie 2021 16:46:05
Problema Parcurgere DFS - componente conexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.24 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];

void read_graph(){
  int m, i, x, y;
  in>>n>>m;
  for( i = 0; i < m; i++ ){
    in>>x>>y;
    noduri[x - 1].next.push_back(y - 1);
    noduri[y - 1].next.push_back(x - 1);

  }

  /*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';
  }*/
}

int 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 = 0; i < n; i++ ){
      //cout<<noduri[i].vizitat<<'\n';
      if( noduri[i].vizitat == 0 ){
        cnt++;
        dfs(i);
      }
    }
    out<<cnt;
    return 0;
}