Cod sursa(job #968565)

Utilizator mitrutstrutMitrea Andrei Ionut mitrutstrut Data 2 iulie 2013 12:24:38
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.91 kb
#include <cstdlib>
#include <fstream>
#include <iostream>
#include <stack>
#include <utility>
#include <vector>
using namespace std;
 
int DFSINDEX = 1;
stack <pair <size_t, size_t>> edges;
 
void dfs (size_t v, size_t parent,
        vector <size_t> &dfsReach, vector <size_t> &dfsIndex,
        vector <vector <size_t>> &G, vector <vector <size_t>> &C)
{
    dfsIndex[v] = dfsReach[v] = DFSINDEX++;
 
    for (auto &n : G[v])
        if (n == parent) continue;
        else if (dfsIndex[n] == 0)
        {
            edges.push (make_pair (v, n));
            dfs (n, v, dfsReach, dfsIndex, G, C);
            if (dfsReach[v] > dfsReach[n])
                dfsReach[v] = dfsReach[n];
 
            if (dfsReach[n] >= dfsIndex[v])
            {
                C.push_back(vector <size_t>());
                int x, y;
                do {
                    x = edges.top().first;
                    y = edges.top().second;
                    edges.pop();
 
                    C.back().push_back (y);
                } while (x != v && y != n);
                C.back().push_back(v);
            }
        }
        else if (dfsReach[v] > dfsReach[n])
            dfsReach[v] = dfsReach[n];
}
 
int main ()
{
    ifstream fin ("biconex.in");
    ofstream fout ("biconex.out");
 
    size_t N, m;
 
    fin >> N >> m;
    vector <vector <size_t>> G(N+1), C;
    vector <size_t> dfsIndex(N+1, 0), dfsReach(N+1);
 
    for (; m; --m)
    {
        int x, y;
        fin >> x >> y;
        G[x].push_back(y);
        G[y].push_back(x);
    }
 
    for (size_t v = 1; v <= N; ++v)
        if (dfsIndex[v] == 0)
            dfs (v, 0, dfsReach, dfsIndex, G, C);
 
    fout << C.size() << '\n';
    for (auto &component : C)
    {
        for (auto &vertex : component)
            fout << vertex << ' ';
        fout << '\n';
    }
    fout.close();
    return EXIT_SUCCESS;
}