Cod sursa(job #1702702)

Utilizator brada01Bradatan Dorin brada01 Data 15 mai 2016 14:35:13
Problema Parcurgere DFS - componente conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.83 kb
#include<fstream>
#include<iostream>

using namespace std;

int a[10][10],c[20],viz[10];
int n,m,prim,ultim,varf;

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

void bf_iterativ() //parcurgerea in latime
{int k;
 while(prim<=ultim)
 {varf=c[prim];
   for(k=1;k<=n;k++)
      if(a[varf][k]==1&&viz[k]==0) //il adaug pe k in coada daca este vecin pt. varf si nu a fost vizitat
            {ultim++;
             c[ultim]=k;
             viz[k]=1;}
  prim++;
      }
}



int main()
{
int x,y;

f>>n>>m;
for(int i=1;i<=m;i++)
  {f>>x>>y;
     a[x][y]=1;
     }
for(int i=1;i<=n;i++){
    viz[i]=0;
}

 int gConexe=0;
 int nd;

 for(int i=1;i<=n;i++)
    if(viz[i]==0)
    {
     nd=i;
     viz[nd]=1;
     prim=ultim=1;
     c[prim]=nd;
     bf_iterativ();
     gConexe++;
    }

   g<<gConexe;
  }