Cod sursa(job #1710952)

Utilizator zalosinGabriel Negoita zalosin Data 30 mai 2016 08:16:11
Problema Parcurgere DFS - componente conexe Scor 50
Compilator cpp Status done
Runda Arhiva educationala Marime 0.71 kb
#include <iostream>
#include <fstream>

using namespace std;
int n,m,x,y,contor;
int matrice[1000][1000];
int vizitat[1000];

void dfs(int g){
    int i;
    vizitat[g] = 1;
    for (i=1;i<=n;i++){
        if ((vizitat[i] == 0)&&((matrice[g][i]==1) || (matrice[i][g]==1)))
            dfs(i);
    }

}

int main()
{
    ofstream out;
    out.open("dfs.out");
    ifstream in;
    in.open("dfs.in");
    in >> n;
    in >> m;
    for (int i = 0; i < m; i++){
        in >> x;
        in >> y;
        matrice[x][y] = matrice[y][x] = 1;
    }
    for (int i=1;i<=n;i++){
        if (vizitat[i]==0){
            contor++;
            dfs(i);
        }
    }
    out<<contor;
    return 0;
}