Cod sursa(job #1390302)

Utilizator japjappedulapPotra Vlad japjappedulap Data 16 martie 2015 22:51:46
Problema Componente biconexe Scor 46
Compilator cpp Status done
Runda Arhiva educationala Marime 1.7 kb
#include <fstream>
#include <vector>
#include <stack>
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 <vector<int>> BiconnectedComponents;
stack <int> Stk;

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

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;
    Stk.push(node);
    for (const int& next : Graph[node])
    {
        if (father == next)
            continue;
        if (Depth[next] == 0)
        {
            DFS(next, node, level+1);
            LowLink[node] = min(LowLink[node], LowLink[next]);
            if (LowLink[next] >= Depth[node])
                Extract(node);
        }
        else
            LowLink[node] = min(LowLink[node], Depth[next]);
    }
};

void Extract(int node)
{
    vector <int> CurentBC;
    while (!Stk.empty() && node != Stk.top())
    {
        CurentBC.push_back(Stk.top());
        Stk.pop();
    }
    CurentBC.push_back(Stk.top());
    BiconnectedComponents.push_back(CurentBC);
};