Cod sursa(job #1003332)

Utilizator kovari_andreiKovari Andrei kovari_andrei Data 30 septembrie 2013 14:12:40
Problema Parcurgere DFS - componente conexe Scor 50
Compilator cpp Status done
Runda Arhiva educationala Marime 0.68 kb
/*
        Depth first - parcurgerea in adancime
*/

#include <iostream>
#include <fstream>

using namespace std;

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

#define limit 10000

long long a[limit][limit],n,s[10000],dump;

void in_graf()
{
    long i,j;
    in>>n>>dump;
    while(in>>i>>j) a[i][j]=a[j][i]=1;
    in.close();
 }

void DF(int nod)
{
    int k;
    s[nod]=1;
    for(k=1;k<=n;k++)
	if(a[nod][k]==1 && s[k]==0) DF(k);
}

int main()
{
     long cont = 0;
     in_graf();
     for(int i=1;i<=n;i++)
        if(!s[i])
            {
                cont++;
                DF(i);
            }

      out<<cont;
      return 0;
}