Cod sursa(job #1161495)

Utilizator Stefex09Stefan Teodorescu Stefex09 Data 31 martie 2014 11:45:58
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.27 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <cstring>
#include <algorithm>

using namespace std;

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

const int MAXN = 100001;
const int MAXM = 200001;

typedef pair <int, int> PII;

class Stack
{
private:
    PII St[MAXM];
    int Size;

public:
    Stack ()
    {
        Size = 0;
        memset (St, 0, sizeof (St));
    }

    inline void push (const int &X, const int &Y)
    {
        Size ++;
        St[Size] = make_pair (X, Y);
    }

    inline void pop ()
    {
        Size --;
    }

    inline PII top ()
    {
        return St[Size];
    }

    inline bool isEmpty ()
    {
        return !Size;
    }
} S;

vector <int> Graf[MAXN];
vector < vector <int> > Sol;
int Low[MAXN], D[MAXN];

void Baga_Componenta (const int &X, const int &Y)
{
    PII top;
    vector <int> Comp;

    do{
        top = S.top ();
        S.pop ();
        Comp.push_back (top.first);
        Comp.push_back (top.second);
    } while (top.first != X || top.second != Y);

    Sol.push_back (Comp);
}

void DFS (int nod, int father)
{
    D[nod] = D[father] + 1;
    Low[nod] = D[nod];

    vector <int> :: iterator it;

    for (it = Graf[nod].begin (); it != Graf[nod].end (); ++ it)
        if (*it != father){
            if (D[*it] == 0){
                S.push (nod, *it);
                DFS (*it, nod);
                Low[nod] = min (Low[nod], Low[*it]);
                if (Low[*it] >= D[nod])
                    Baga_Componenta (nod, *it);
            }
            else
                Low[nod] = min (Low[nod], D[*it]);
        }
}

int main()
{
    int N, M, a, b, i;

    in >> N >> M;

    for (i = 1; i <= M; i ++){
        in >> a >> b;
        Graf[a].push_back (b);
        Graf[b].push_back (a);
    }

    DFS (1, 0);

    int Ans = Sol.size ();
    vector <int> :: iterator it;
    out << Ans << "\n";
    for (size_t i = 0; i < Ans; i ++){
        sort (Sol[i].begin (), Sol[i].end ());
        Sol[i].erase (unique (Sol[i].begin (), Sol[i].end ()), Sol[i].end ());

        for (it = Sol[i].begin (); it != Sol[i].end (); ++ it)
            out << *it << " ";

        out << "\n";
    }

    return 0;
}