Cod sursa(job #2338262)

Utilizator Raul09062000Ianos Raul-Daniel Raul09062000 Data 7 februarie 2019 11:30:15
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.04 kb
#include <bits/stdc++.h>

#define nmax 100005

using namespace std;

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

deque <int> vecini;
bitset <nmax> vizitat;
vector <int> muchii[nmax];
int n,m,cnt;

void alocare()
{
    for(int i=1; i<=n; i++)
        vizitat[i]=0;
}

void DFS(int nc)
{
    int nod;
    while(!vecini.empty())
    {
        nod=vecini.front();
        vecini.pop_front();
        for(int i=0; i<muchii[nod].size(); i++)
            if(!vizitat[muchii[nod][i]])
            {
                vecini.push_back(muchii[nod][i]);
                vizitat[muchii[nod][i]]=1;
                DFS(muchii[nod][i]);
            }
    }
}

int main()
{
    f>>n>>m;
    for(int i=1; i<=m; i++)
    {
        int a,b;
        f>>a>>b;
        muchii[a].push_back(b);
        muchii[b].push_back(a);
    }

    alocare();

    for(int i=1; i<=n; i++)
        if(!vizitat[i])
        {
            cnt++;
            vecini.push_back(i);
            DFS(i);
        }


    g<<cnt;
    return 0;
}