Cod sursa(job #2538398)

Utilizator marapopescuMara Popescu marapopescu Data 4 februarie 2020 18:32:30
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.55 kb
#include <iostream>
#include <vector>
#include <fstream>

using namespace std;

ifstream f("dfs.in");
ofstream g("dfs.out");
int n,m,nr;
vector <int> v[100010];
bool sel[100010];

void dfs(int x)
{
    sel[x]=true;
    for(auto i:v[x])
        if(sel[i]==false) dfs(i);

}
int main()
{

    f>>n>>m;
    for(int i=1;i<=m;i++)
    {   int x,y;
        f>>x>>y;
        v[x].push_back(y);
        v[y].push_back(x);

    }
    nr=0;
    for(int j=1;j<=n;j++)
    {if(sel[j]==false) {nr++;dfs(j);}
    }
    g<<nr;
    return 0;
}