Cod sursa(job #2429628)

Utilizator mariasmmskklns mariasmm Data 10 iunie 2019 16:18:39
Problema Parcurgere DFS - componente conexe Scor 55
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.39 kb
#include <iostream>
#include <stack>
#include <fstream>
#include <vector>
using namespace std;
const int NMAX = 10002;
stack <int> s;
vector <int> v[2*NMAX];
bool vizitat[NMAX]={0};
int N, M;
void citire()
{
    ifstream f("dfs.in");
    f>>N>>M;
    int n1, n2;
    for (int i=0; i<M; i++)
    {
        f>>n1>>n2;
        v[n1].push_back(n2);
        v[n2].push_back(n1);
    }
}

void afisare(int componenteConexe)
{
    ofstream g("dfs.out");
    g<<componenteConexe;
}

void dfs(int nod)
{
    int nodCurent,next;
    nodCurent=nod;
    if(!s.empty())
    {
        vizitat[nodCurent]=true;
        bool ok=false;
        for (int i=0; i<v[nodCurent].size(); i++)
            {
                next=v[nodCurent][i];
                if (vizitat[next]==false)
                {
                    s.push(next);
                    ok=true;
                    break;
                }
            }
        if (ok)
            dfs(next); else
        {
            s.pop();
            if (!s.empty())
            {
            next=s.top();
            dfs(next);
            }
        }
    }
}

int main()
{
    int componenteConexe=0;
    citire();
    for (int i=1; i<=N; i++)
        if (!vizitat[i])
        {
            s.push(i);
            dfs(i);
            componenteConexe++;
        }
    afisare(componenteConexe);
    return 0;
}