Cod sursa(job #1389778)

Utilizator japjappedulapPotra Vlad japjappedulap Data 16 martie 2015 17:30:31
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.77 kb
#include <fstream>
#include <vector>
#include <stack>
using namespace std;

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

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

int N, M;

int Ind[Nmax];      //Ind[i] = adancimea nodului i in arborele DF
int L[Nmax];        //L[i] = cea mai mica adancime a vecinilor nodului i
bool Viz[Nmax];
vector <int> G[Nmax], Comp;
vector < vector<int> > BCC;
stack <int> S;


void Read();
void DFS(int node);
void Biconnected(int node);

int main()
{
    Read();
    DFS(1);
    Biconnected(1);
    os << BCC.size();
    os << '\n';
    for (const auto& C : BCC)
    {
        for (const int& i : C)
            os << i << ' ';
        os << '\n';
    }

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

void Read()
{
    is >> N >> M;
    for (int i = 1, a, b; i <= M; ++i)
    {
        is >> a >> b;
        G[a].push_back(b);
        G[b].push_back(a);
    }
    for (int i = 1; i <= N; ++i)
        L[i] = oo;
};

int ActualDepth;

void DFS(int node)
{
    Viz[node] = 1;
    Ind[node] = ++ActualDepth;
    for (const int& next : G[node])
        if (Ind[next] == 0)
        {
            DFS(next);
            L[node] = min(L[node], L[next]);
        }
        else
            L[node] = min(L[node], Ind[next]);
    --ActualDepth;
};

void Biconnected(int node)
{
    Viz[node] = 0;
    S.push(node);
    for (const int& next : G[node])
        if (Viz[next])
        {
            Biconnected(next);
            if (L[next] >= Ind[node])
            {
                Comp.clear();
                for (;!S.empty() && S.top() != next; S.pop())
                    Comp.push_back(S.top());
                Comp.push_back(S.top()), S.pop();
                Comp.push_back(node);
                BCC.push_back(Comp);
            }
        }
};