Cod sursa(job #2793412)

Utilizator andreea_07Andreea Georgescu andreea_07 Data 3 noiembrie 2021 17:06:28
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.74 kb
#include <iostream>
#include <queue>
#include <map>
#include <vector>
#include <fstream>


using namespace std;

int n,m,viz[100005],nrcomp=0;
 ifstream fin("dfs.in");
ofstream fout("dfs.out");

void dfs(vector<int> graf[100005],int s)
{ int i;
  viz[s]=1;
  //cout<<s<<" ";
vector<int>::iterator it;
    for ( it = graf[s].begin(); it != graf[s].end(); ++it)
       if (!viz[*it]) dfs(graf,*it);
}


void conex(  vector<int>graf[100005])
{ int i;
  for(i=1;i<=n;i++)
    if (viz[i]==0) { nrcomp++; dfs(graf,i);}
  fout<<nrcomp;
}


int main()
{
vector<int> graf[100005];
int x,y;
fin>>n>>m;
for(int i=0;i<m;i++)
    {fin>>x>>y;
    graf[x].push_back(y);
    graf[y].push_back(x);}
conex(graf);
    return 0;
}