Cod sursa(job #1810042)

Utilizator eilerGabriel-Ciprian Stanciu eiler Data 19 noiembrie 2016 15:50:53
Problema Parcurgere DFS - componente conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.82 kb
#include <fstream>
#include <vector>
using namespace std;

int n, m, u, nr;
vector <int> c(100000);
vector <bool> v(100000);
vector <vector <bool> > a(100000);

void adancime(int k){
    int i;

    u++;
    c[u]=k;
    v[k]=true;
    for (i=0; i<n; i++)
        if (a[k][i]==true && v[i]==false)
					adancime(i);
}

int main(){
    int i, j, k;

    fstream f;

    f.open("dfs.in", ios_base::in);
    f >> n >> m;
    for (k=0; k<n; k++)
			for (i=0; i<n; i++)
				a[i][k]=a[k][i]=false;
    for (k=0; k<m; k++){
        f >> i >> j;
        i--; j--;
        a[i][j]=a[j][i]=true;
    }
    f.close();

    for (i=0; i<n; i++)
        if (v[i]==false){
					u=0;
					adancime(i);
					nr++;
        }

    f.open("dfs.out", ios_base::out);
    f << nr;
    f.close();

    return 0;
}