Cod sursa(job #2277264)

Utilizator DanutAldeaDanut Aldea DanutAldea Data 5 noiembrie 2018 22:12:04
Problema Parcurgere DFS - componente conexe Scor 45
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.59 kb
#include <fstream>
#include <vector>
using namespace std;

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

int n,i,j,cnt,f[100010];
vector <int> l[100010];

void dfs(int a){
    for(int k=0;k<l[a].size();k++){
        if(f[l[a][k]]==0){
            f[l[a][k]]=cnt;
            dfs(l[a][k]);
        }
    }
}

int main(){
    fin>>n;

    while(fin>>i>>j){
        l[i].push_back(j);
        l[j].push_back(i);
    }

    for(j=1;j<=n;j++){
        if(f[j]!=0)
            continue;

        f[j]=++cnt;
        dfs(j);
    }

    fout<<cnt;

    return 0;
}