Cod sursa(job #2852884)

Utilizator tiut_cristianTiut Cristian tiut_cristian Data 19 februarie 2022 17:41:36
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.17 kb
#include <bits/stdc++.h>

using namespace std;

int n, m;

struct node
{
    vector<int> vecini;
    bool vizitat;
}v[100001];

void citire()
{
    ifstream fin("dfs.in");
    fin >> n >> m;
    for(int i = 1; i <= m; i++)
    {
        int a, b;
        fin >> a >> b;
        v[a].vecini.push_back(b);
        v[b].vecini.push_back(a);
    }
}

void dfs(int inceput)
{
    stack<pair<int,int>> st;
    st.push({inceput,0});
    v[inceput].vizitat = true;

    while(!st.empty())
    {
        auto &t = st.top();
        int nod = t.first;
        int i = t.second;

        if(i < v[nod].vecini.size())
        {
            int x = v[nod].vecini[i];
            t.second = i+1;

            if(!v[x].vizitat)
            {
                v[x].vizitat = true;
                st.push({x,0});
            }
        }
        else
            st.pop();
    }
}

void afisare()
{
    ofstream fout("dfs.out");
    int cnt = 0;
    for(int i = 1; i <= n; i++)
        if( !v[i].vizitat )
        {
            cnt++;
            dfs(i);
        }
    fout << cnt;
}

int main()
{
    citire();
    afisare();

    return 0;
}