Cod sursa(job #2022009)

Utilizator Mihai_PredaPreda Mihai Dragos Mihai_Preda Data 15 septembrie 2017 12:23:38
Problema Componente biconexe Scor 46
Compilator cpp Status done
Runda Arhiva educationala Marime 2.04 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>

using namespace std;

const int nMax = 100005;

class graf
{
    public:
        vector<int> vecini[nMax];
        void AddEdge(int x, int y)
        {
            vecini[x].push_back(y);
            vecini[y].push_back(x);
        }
        void GetBiComp(vector<vector<int> > &ret, int current = 1, int father = 0)
        {
            noduri.push(current);
            lowPoint[current] = nivel[current] = nivel[father] + 1;
            for(auto v:vecini[current])
            {
                if(nivel[v])
                    lowPoint[current] = min(lowPoint[current], nivel[v]);
                else
                {
                    GetBiComp(ret, v, current);

                    lowPoint[current] = min(lowPoint[current], lowPoint[v]);
                    if(lowPoint[v] == nivel[current])
                    {
                        ret.resize(ret.size() + 1);
                        int t;
                        while(noduri.top() != current)
                        {
                            t = noduri.top();
                            noduri.pop();

                            ret.back().push_back(t);
                        }
                        ret.back().push_back(current);
                    }
                }
            }
        }
    private:
        stack<int> noduri;
        int nivel[nMax];
        int lowPoint[nMax];
};

int n, m;
graf g;
vector<vector<int> > rasp;

void citire()
{
    ifstream in("biconex.in");
    in >> n >> m;
    int x, y;
    for(int i = 1; i <= m; ++i)
    {
        in >> x >> y;
        g.AddEdge(x, y);
    }
    in.close();
}

void afisare()
{
    ofstream out("biconex.out");
    out << rasp.size() << "\n";
    for(int i = 0; i < rasp.size(); ++i)
    {
        for(auto x:rasp[i])
            out << x << " ";
        out << "\n";
    }
    out.close();
}

int main()
{
    citire();
    g.GetBiComp(rasp);
    afisare();
    return 0;
}