Cod sursa(job #2201314)

Utilizator Andreea_DanielaAndreea Guster Andreea_Daniela Data 4 mai 2018 11:05:15
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.32 kb
#include <fstream>
#include <vector>
#include <stack>
#include <algorithm>
#define Nmax 100000

using namespace std;

int idx;
vector<int> comp_biconexe[Nmax + 2];
stack<int> vf_comp_biconexe;

void citire(int &n, vector<int>* &la)
{
    ifstream f("biconex.in");
    int m, x, y;
    f >> n >> m;

    la = new vector<int>[n+1];

    for(int i=1; i<=m; i++)
    {
        f >> x >> y;
        la[x].push_back(y);
        la[y].push_back(x);
    }
    f.close();
}

void DFS(const int& nod, const int& nod_vechi, vector<int>* la, bool* viz, int* nivel, int* nivel_min)
{
    viz[nod] = true;
    nivel[nod] = nivel[nod_vechi] + 1;
    nivel_min[nod] = nivel[nod];

    vf_comp_biconexe.push(nod);

    for (int i = 0; i < (int) la[nod].size(); i++)
    {
       int nod_curent = la[nod][i];

        if (!viz[nod_curent]) //daca e muchie de traversare
        {
            DFS(nod_curent, nod, la, viz, nivel, nivel_min);

            nivel_min[nod] = min(nivel_min[nod], nivel_min[nod_curent]);

            if (nivel[nod] <= nivel_min[nod_curent])
            {
                idx++;
                while (vf_comp_biconexe.top() != nod_curent && !vf_comp_biconexe.empty())
                {
                    comp_biconexe[idx].push_back(vf_comp_biconexe.top());
                    vf_comp_biconexe.pop();
                }
                comp_biconexe[idx].push_back(nod_curent);

                if (!vf_comp_biconexe.empty())
                    vf_comp_biconexe.pop();

                comp_biconexe[idx].push_back(nod);
            }
        }
        else  //daca e muchie de intoarcere
        {
            if (nod_curent != nod_vechi)
            {
                nivel_min[nod] = min(nivel_min[nod], nivel[nod_curent]);
            }
        }
    }
}

int main()
{
    int i, j, n;
    vector <int> *la;

    citire(n, la);

    bool *viz = new bool[n+1]();
    int *nivel = new int[n+1]();
    int *nivel_min = new int[n+1]();

    DFS(1, 0, la, viz, nivel, nivel_min);

    ofstream fout("biconex.out");
    fout << idx << '\n';
    for (i = 1; i <= idx; i++)
    {
        for (j = 0; j < (int) comp_biconexe[i].size(); j++)
        {
            fout << comp_biconexe[i][j] << ' ';
        }
        fout << '\n';
    }
    fout.close();

    return 0;
}