Cod sursa(job #1650136)

Utilizator cristinelulCristian Virga cristinelul Data 11 martie 2016 16:47:33
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.69 kb
#include <fstream>
#include <vector>
#define nmax 100005

using namespace std;

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

vector <int> v[nmax];
int n,m,viz[nmax];
void citire()
{
   int i,a,b;
   fin>>n>>m;
   for(i=1;i<=m;i++)
   {
      fin>>a>>b;
      v[a].push_back(b);
      v[b].push_back(a);
   }
}
void dfs(int x)
{
   int i;
   for(i=0;i<v[x].size();i++)
      if(viz[v[x][i]]==0)
      {
         viz[v[x][i]]=1;
         dfs(v[x][i]);
      }
}
int main()
{
   int i,nr=0;
   citire();
   for(i=1;i<=n;i++)
      if(viz[i]==0)
      {
         viz[i]=1;
         dfs(i);
         nr++;
      }
   fout<<nr;
   fout.close();
   return 0;
}