Cod sursa(job #1572216)

Utilizator japjappedulapPotra Vlad japjappedulap Data 18 ianuarie 2016 20:03:57
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.78 kb
/*




*/
#include <algorithm>
#include <fstream>
#include <cstring>
#include <vector>
#include <stack>
using namespace std;

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

const int Nmax = 100001;
using PII = pair<int,int>;
int N, M;
vector <int> Graph[Nmax];

stack <PII> S;      //tata si fiu
vector <vector<int> > BCCs;

int TreeEdgesFromRoot, BackEdges;
int Link[Nmax], Depth[Nmax], F[Nmax];
bool Viz[Nmax];
void DFS(int x, int d);
void Extract(int x, int y);

int main()
{
    is >> N >> M;
    for (int a, b; M; --M)
    {
        is >> a >> b;
        Graph[a].push_back(b);
        Graph[b].push_back(a);
    }


    DFS(1, 1);

    os << BCCs.size() << '\n';
    for (auto& BC : BCCs)
    {
        sort(BC.begin(), BC.end());
        for (const int& x : BC)
            os << x << ' ';
        os << '\n';
    }
    is.close();
    os.close();
}

void DFS(int x, int d)
{
    Depth[x] = Link[x] = d;
    Viz[x] = 1;
    if (d == 2)
        TreeEdgesFromRoot++;
    for (const int& y : Graph[x])
    {
        if (y == F[x]) continue;    //daca e tata, sarim peste
        if (Viz[y] == 0)            //treeedge
        {
            S.push({x, y});
            F[y] = x;
            DFS(y, d+1);
            Link[x] = min(Link[x], Link[y]);
            if (Link[y] >= Depth[x])  //critic
                Extract(x, y);

        }
        else                        //backedge
            Link[x] = min(Link[x], Depth[y]);
    }
};

void Extract(int x, int y)
{
    vector <int> C;
    int X, Y;
    do
    {
        X = S.top().first;
        Y = S.top().second;
        S.pop();
        C.push_back(Y);
    }
    while (X != x && Y != y && !S.empty());

    C.push_back(x);
    BCCs.push_back(C);
};