Cod sursa(job #2192626)

Utilizator PushkinPetolea Cosmin Pushkin Data 6 aprilie 2018 19:02:28
Problema Parcurgere DFS - componente conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.16 kb
#include <iostream>
#include <bits/stdc++.h>
#include <fstream>
using namespace std;
ifstream f("DFS.in");
ofstream g("DFS.out");
vector<vector<int>> G;
unsigned int n, a, i, res;
vector<bool> viz;
void rd()
{
    int x, y;
    f>>n>>a;
    viz.resize(n+3);
    G.resize(n+3);
    while(f>>x>>y)
    {
        G[x].push_back(y);
        G[y].push_back(x);
    }
}
struct nod
{
    int x, j;/// i-ul din for la care am ramas
    nod(int nr, int pas)
    :x(nr), j(pas){}
};
stack<nod> s;
void DFS(int x)
{
    viz[x]=1;
    s.push(nod(x, 0));
    while(s.size())
    {
        x=s.top().x;
        for(i=s.top().j;i<G[x].size();i++)
            if(!viz[G[x][i]])
            {
                viz[G[x][i]]=1;
                s.top().j=i+1;
                s.push(nod(G[x][i], 0));
                break;
            }
        if(i>=G[x].size())
            s.pop();
    }
}
int nxt()
{
    for(i=1;i<=n;i++)
        if(!viz[i])return i;
    return 0;
}
int main()
{
    rd();
    a=1;
    while(a)
    {
        DFS(a);
        a=nxt();
        res++;
    }
    g<<res;
    f.close();
    g.close();
    return 0;
}