Cod sursa(job #2668459)

Utilizator mihaimbMihai Badea mihaimb Data 4 noiembrie 2020 22:09:57
Problema Parcurgere DFS - componente conexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.01 kb
#include <iostream>
#include <vector>
#include <bitset>
#include <stack>


using namespace std;

int main()
{

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

    int n,m,x,y;

    fin>>n>>m;

    vector<int> L[100001];

    for(int i=0; i<m; i++)
    {
        fin>>x>>y;

        L[x].push_back(y);
        L[y].push_back(x);
    }


    bitset<100001> B;

    int conexe = 0;

    for(int i=1; i<=n; i++)
    {
        if(!B[i])
        {

            stack<int> S;

            S.push(i);

            while(!S.empty())
            {
                int t = S.top();
                S.pop();
                B[t]=1;
                for(int j=0; j<L[t].size(); j++)
                {
                    if(!B[L[t][j]])
                    {
                        S.push(L[t][j]);
                    }

                }
            }

            conexe++;
        }
    }


    fout<<conexe<<'\n';

    fin.close();
    fout.close();

    return 0;
}