Cod sursa(job #1988208)

Utilizator AdrianaMAdriana Moisil AdrianaM Data 2 iunie 2017 13:46:43
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.64 kb
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;

#define file "dfs"

using VI = vector<int>;
using VVI = vector<VI>;

int n, m;
VVI g, C;

void read()
{
    int x, y;
    ifstream is(file".in", ios::in);

    is >> n >> m;
    g = VVI(n + 1);

    for (int i = 1; i <= m; ++i)
    {
        is >> x >> y;
        g[x].push_back(y);
        g[y].push_back(x);
    }
    is.close();
}

void solve()
{
    VI comp, c(n + 1), p(n + 1), o(n + 1), N(n + 1);
    int s = 1, i, j, E = 0;

    while (E < n)
    {
        if (!p[s])
        {
            C.push_back(comp);
            comp.clear();

            comp.push_back(s);
            p[s] = s;
            o[s] = ++E;
            i = s;
            while (N[i] != g[i].size() || i != s)
                if (N[i] == g[i].size())
                    i = p[i];
                else
                {
                    j = g[i][N[i]++];
                    if (!p[j])
                    {
                        p[j] = i;
                        i = j;
                        c[i] = C.size();
                        comp.push_back(i);
                        o[i] = ++E;
                    }
                }
        }
        ++s;
    }
}

void write()
{
    ofstream os(file".out", ios::out | ios::trunc);
    os << C.size() << "\n";
   /* for_each(C.begin(), C.end(), [&os](const VI& comp){
        for_each(comp.begin(), comp.end(), [&os](int x){
            os << x << " ";
        });
        os << "\n";
    });*/
    os.close();
}

int main()
{
    read();
    solve();
    write();
    return 0;
}