Cod sursa(job #1295438)

Utilizator Vele_GeorgeVele George Vele_George Data 19 decembrie 2014 15:01:20
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.75 kb
#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

long long n,m,i,j,k;
int x,y;
vector< vector < int > > nod;
vector< bool > valid;



void dfs(int x){

    valid[x]=true;
    for(int j=0; j<nod[x].size(); j++)
        if (valid[nod[x][j]]==false) dfs(nod[x][j]);

}

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


    f>>n>>m;
    nod.resize(n+1);
    valid.resize(n+1);
    for(i=1; i<=m; i++){
        f>>x>>y;
        nod[x].push_back(y);
        nod[y].push_back(x);
    }
    for(i=1; i<=n; i++) valid[i]=false;

    k=0;
    for(i=1; i<=n; i++)
        if (valid[i]==false){k++; dfs(i);}


    g<<k;






    f.close();
    g.close();

    return 0;
}