Cod sursa(job #3004658)

Utilizator DevilonnetPescar Denis Devilonnet Data 16 martie 2023 15:17:22
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.55 kb
#include<fstream>
#include<vector>
#include<queue>

using namespace std;
ifstream cin("dfs.in");
ofstream cout("dfs.out");
int n,m,P[100001],nrcomp;
vector<vector<int>>G(200001);

void DFS(int nod)
{
    P[nod]=1;
    for(auto x:G[nod])
        if(!P[x])
            DFS(x);
}
int main()
{
    cin>>n>>m;
    for(int i=1,x,y;i<=m;++i)
        {
            cin>>x>>y;
            G[x].push_back(y);
            G[y].push_back(x);
        }
    for(int i=1;i<=n;++i)
        if(!P[i])
            nrcomp++,DFS(i);
    cout<<nrcomp;
}