Cod sursa(job #1259562)

Utilizator AraldaAralda Pacurar Aralda Data 10 noiembrie 2014 10:41:47
Problema Parcurgere DFS - componente conexe Scor 5
Compilator cpp Status done
Runda Arhiva educationala Marime 0.58 kb
#include <fstream>

using namespace std;
ifstream fi("dfs.in");
ofstream fo("dfs.out");

int i,n,m,l,c,comp,nc;
bool a[20000][20000],v[20000];

void DFS(int x)
 {
  int i;
  for(i=1;i<=n;i++)
   if(a[nc][i] and v[i]==false)
    {
     v[i]=true;

     DFS(i);
    }

 }

int main()
{
    fi>>n>>m;
    for(i=1;i<=m;i++)
     {
      fi>>l>>c;
      a[l][c]=a[c][l]=true;
     }
    nc=1;
    for(i=1;i<=n;i++)
     {

      if(v[i]==false)
      {
       v[i]=true;
       DFS(i);
       comp++;
      }
      nc++;
     }
    fo<<comp;
    return 0;
}