Cod sursa(job #2796137)

Utilizator HatersMcCristian Ioan HatersMc Data 7 noiembrie 2021 17:24:17
Problema Parcurgere DFS - componente conexe Scor 45
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.65 kb
#include <fstream>
#include <vector>
#include <stack>
using namespace std;
ifstream f("dfs.in");
ofstream g("dfs.out");
vector<bool> viz(100001,false);
void dfs( int n, vector<vector<int>> mat )
{
    viz[n]=true;
    for(auto a : mat[n])
        if(!viz[a])
            dfs(a,mat);
}
int n,m;
int main() {
    f >> n >> m ;
    vector<vector<int> > mat(n + 1);
    for (int i = 0; i < m; ++i) {
        int a, b;
        f >> a >> b;
        mat[a].push_back(b);
        mat[b].push_back(a);
    }

    int nr= 0 ;
    for(int i=1 ; i <= n ; ++i)
        if(!viz[i])
        {
            dfs(i,mat);
            nr++;
        }
        g<<nr;

    return 0;
}