Cod sursa(job #2155012)

Utilizator Y0da1NUME JMECHER Y0da1 Data 7 martie 2018 15:23:17
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.07 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>

#define maxn 100005
#define maxm 200005

using namespace std;

int N, M; int nr;
vector <int> G [maxn];  //graful repr prin lista de adiacenta
int nivel[maxn], low[maxn], tata[maxn];     //nivelu in defeu, unde duce muchia de intoarcere si tatal fiecarui nod in arborele dfului
vector < vector <int> > sol;   //matrice
bool vizitat[maxn]; //ii trebe la defeu
stack<int> stiva;

void biconex(int x)
{
    vizitat[x] = 1;
    nivel[x] = nivel[tata[x]] + 1;
    low[x] = nivel[x];  //presupunem init ca toate nodurile sunt pct de articulatie si nu au muchii de intoarcere

    stiva.push(x);

    for(int i = 0; i < G[x].size(); ++i)
    {
        int succ = G[x][i];
        if(vizitat[succ])   //am gasit o muchie de intoarcere
        {
            if(succ != tata[x])
                low[x] = min(low[x], nivel[succ]);
            continue;
        }
        tata[succ] = x;
        biconex(succ);
        low[x] = min(low[succ], low[x]);

        if(nivel[x] <= low[succ])   //am gasit un punct de articulatie
        {
            sol.push_back(vector<int>(0));
            int k;
            do{
                k = stiva.top();
                stiva.pop();
                sol[nr].push_back(k);   //adaug elementele din stiva (subarborele df) intr-o singura componenta
            }while(k!=succ);
            sol[nr].push_back(x);   //trec la urmatoarea componenta biconexa
            ++nr;
        }
    }
}

int main()
{
    ifstream in ("biconex.in");
    ofstream out ("biconex.out");
    in>>N>>M;
    for(int i = 0; i < M; ++i)
    {
        int x, y;
        in>>x>>y;
        G[x].push_back(y);
        G[y].push_back(x);
    }
    for(int i = 1; i <= N; ++i)
        if (!vizitat[i])
        {
            tata[i]=0;
            biconex(i);
        }
    out<<nr<<"\n";

    for(int i = 0; i < sol.size(); ++i)
    {
        for(auto it = sol[i].begin(); it != sol[i].end(); ++it)
            out<<*it<<" ";
        out<<'\n';
    }
    return 0;
}