Cod sursa(job #1475669)

Utilizator cristinelulCristian Virga cristinelul Data 24 august 2015 11:39:44
Problema Parcurgere DFS - componente conexe Scor 50
Compilator cpp Status done
Runda Arhiva educationala Marime 0.67 kb
#include <fstream>

using namespace std;

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

int n,m,g[1001][1001],viz[100001];
void citire()
{
   int i,a,b;
   fin>>n>>m;
   for(i=1;i<=m;i++)
   {
      fin>>a>>b;
      g[a][0]++;
      g[b][0]++;
      g[a][g[a][0]]=b;
      g[b][g[b][0]]=a;
   }
}
void dfs(int x)
{
   int i;
   for(i=1;i<=g[x][0];i++)
      if(viz[g[x][i]]==0)
      {
         viz[g[x][i]]=1;
         dfs(g[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;
}