Cod sursa(job #2663390)

Utilizator Alinnus1Anghel Alin Alinnus1 Data 26 octombrie 2020 11:51:22
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.04 kb
#include <bits/stdc++.h>

using namespace std;

int N, M,sol;
const int NMAX = 100005;
vector<int> Muchii [NMAX];
stack <int> Stiva ;
bool Vizita[NMAX];

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

void citire ()
{
    f>>N>>M;
    for (int i=1;i<=M;i++)
    {
        int x,y;
        f >> x >> y;
        Muchii[x].push_back(y);
        Muchii[y].push_back(x);
    }
}

void dfs()
{
    int x =0;
    for ( int i =1;i<=N ; i++)
    {
        if(!Vizita[i])
        {
            sol++;
            Stiva.push(i);
            while(!Stiva.empty())
            {
                x=Stiva.top();
                Stiva.pop();
                if(!Vizita[x])
                {
                    Vizita[x]=1;
                    for(int j=0;j<Muchii[x].size();j++)
                    {
                        Stiva.push(Muchii[x][j]);
                    }
                }
            }
        }
    }
}

void solve()
{
    dfs();
    g<<sol;
}

int main()
{
    citire();
    solve();
    return 0;
}