Cod sursa(job #1167273)

Utilizator tester9x9Tester9x9 tester9x9 Data 4 aprilie 2014 18:37:04
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.3 kb
#include <fstream>
#include <algorithm>
#include <vector>
#include <stack>

using namespace std;

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

int N, M;
vector< vector<int> > G, Components;
vector<int> Level, LowLink;
stack< pair<int, int> > Stack;

void Read ()
{
    f >> N >> M;

    G.resize(N);
    Level.resize(N, 0);
    LowLink.resize(N, 0);

    for (int i=0; i<M; i++)
    {
        int a, b;
        f >> a >> b;
        G[a-1].push_back(b-1);
        G[b-1].push_back(a-1);
    }

    f.close();
}

void DF (int node, int father)
{
    LowLink[node]=Level[node];

    for (vector<int>::iterator it=G[node].begin(); it!=G[node].end(); ++it)
    {
        if (*it==father)
            continue;

        if (Level[*it]==0)
        {
            Level[*it]=Level[node]+1;
            Stack.push(make_pair(node, *it));
            DF(*it, node);

            if (LowLink[*it]>=Level[node])
            {
                vector<int> Aux;

                for (; !Stack.empty() && Stack.top()!=make_pair(node, *it); Stack.pop())
                {
                    Aux.push_back(Stack.top().first);
                    Aux.push_back(Stack.top().second);
                }
                if (!Stack.empty() && Stack.top()==make_pair(node, *it))
                {
                    Aux.push_back(Stack.top().first);
                    Aux.push_back(Stack.top().second);
                    Stack.pop();
                }

                sort(Aux.begin(), Aux.end());
                Aux.resize(unique(Aux.begin(), Aux.end())-Aux.begin());

                Components.push_back(Aux);
            }

            LowLink[node]=min(LowLink[node], LowLink[*it]);
        }
        else
            LowLink[node]=min(LowLink[node], Level[*it]);
    }
}

void Solve ()
{
    for (int i=0; i<N; i++)
        if (!Level[i])
        {
            Level[i]=1;
            DF(i, -1);
        }
}

void Print ()
{
    g << Components.size() << '\n';

    for (size_t i=0; i<Components.size(); i++)
    {
        for (vector<int>::iterator it=Components[i].begin(); it!=Components[i].end(); ++it)
            g << (*it)+1 << ' ';
        g << '\n';
    }

    g.close();
}

int main ()
{
    Read();
    Solve();
    Print();

    return 0;
}