Cod sursa(job #1390332)

Utilizator japjappedulapPotra Vlad japjappedulap Data 16 martie 2015 23:06:03
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.84 kb
#include <fstream>
#include <vector>
#include <stack>
#include <set>
using namespace std;

ifstream is ("biconex.in");
ofstream os ("biconex.out");

const int Nmax = 100001;
const int INF = 0x3f3f3f3f;

int Nodes, Edges;
int Depth[Nmax], LowLink[Nmax];

vector <int> Graph[Nmax];
vector < set<int> > BiconnectedComponents;
stack < pair<int, int> > Stk;

void Read();
void DFS(int node, int father, int level);
void Extract(int node, int next);

int main()
{
    Read();
    DFS(1, 0, 1);

    os << BiconnectedComponents.size() << '\n';
    for (const auto& CurentBC : BiconnectedComponents)
    {
        for (const int& i : CurentBC)
            os << i << ' ';
        os << '\n';
    }

    is.close();
    os.close();
}

void Read()
{
    is >> Nodes >> Edges;
    for (int x, y; Edges; --Edges)
    {
        is >> x >> y;
        Graph[x].push_back(y);
        Graph[y].push_back(x);
    }
};

void DFS(int node, int father, int level)
{
    Depth[node] = LowLink[node] = level;
    for (const int& next : Graph[node])
    {
        if (father == next)
            continue;
        if (Depth[next] == 0)
        {
            Stk.push({node, next});

            DFS(next, node, level+1);
            LowLink[node] = min(LowLink[node], LowLink[next]);

            if (LowLink[next] >= Depth[node])
                Extract(node, next);
        }
        else
            LowLink[node] = min(LowLink[node], Depth[next]);
    }
};

void Extract(int node, int next)
{
    set <int> CurentBC;
    int X, Y;
    do
    {
        X = Stk.top().first;
        Y = Stk.top().second;
        Stk.pop();
        CurentBC.insert(X);
        CurentBC.insert(Y);
    }
    while (!Stk.empty() && node != X && next != Y);
    BiconnectedComponents.push_back(CurentBC);
};