Cod sursa(job #1571262)

Utilizator japjappedulapPotra Vlad japjappedulap Data 17 ianuarie 2016 17:45:28
Problema Componente biconexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 3.17 kb
/// prima parte e problema clasica a componentelor biconexe,
/// dupaia urmeaza niste functii care gasesc punctele de articulatie si muchiile critice
#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);

/// ADD-ONS

int Father[Nmax], RootSons;
vector <int> Articulation();
vector < pair<int, int> > Bridges();

///

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';
    }


    os << '\n' << '\n';

    vector <int> PA = Articulation();
    for (const int& i : PA)
        os << i << ' ';
    os << '\n' << '\n';

    vector < pair<int, int> > CE = Bridges();
    for (const auto& i : CE)
        os << i.first << ' ' << i.second << '\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)
{
    if (level == 2) RootSons++;             ///ADD-ON

    Depth[node] = LowLink[node] = level;
    for (const int& next : Graph[node])
    {
        if (father == next)
            continue;
        if (Depth[next] == 0)
        {

            Father[next] = node;            ///ADD-ON

            Stk.push({node, next});
            DFS(next, node, level+1);
            LowLink[node] = min(LowLink[node], LowLink[next]);

            if (LowLink[i] == Depth[Father[i]] || LowLink[i]-1 == Depth[Father[i]] )
                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);
};

/// ADD-ONS

vector <int> Articulation()
{
    bool Art[Nmax];
    vector <int> Sol;
    if (RootSons > 1) Art[1] = 1;
    for (int i = 2; i <= Nodes; ++i)
        if (Father[i] != 1 && (LowLink[i] == Depth[Father[i]] || LowLink[i]-1 == Depth[Father[i]] ))
            Art[Father[i]] = 1;
    for (int i = 1; i <= Nodes; ++i)
        if (Art[i] == 1)
            Sol.push_back(i);
    return Sol;
};

vector < pair<int, int> > Bridges()
{
    vector <pair<int,int> > Sol;
    for (int i = 2; i <= Nodes; ++i) //sarim peste nodul 1 ptr ca nu are tata
        if (LowLink[i] > Depth[Father[i]])
            Sol.push_back({Father[i], i});
    return Sol;
};