Cod sursa(job #2665247)

Utilizator iulia_caciucunescuIulia Caciucunescu iulia_caciucunescu Data 30 octombrie 2020 14:06:47
Problema Componente biconexe Scor 44
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 3.41 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
#include <set>
using namespace std;

int niv_punct = 0;
stack<pair<int, int> > sol;
vector<set<int> > comp;
void punct_critic(int start, vector<vector<int> > adiacenta, vector<bool> &critic, vector<bool> &viz, vector<int> &niv, vector<int> &minim, vector<int> &tata)
{
    int child = 0;
    viz[start] = true;
    niv[start] = minim[start] = niv_punct++;

    for(int nod : adiacenta[start])
    {
        if(!viz[nod])
        {
            child++;
            tata[nod] = start;
            sol.push(make_pair(start, nod));
            punct_critic(nod, adiacenta, critic, viz, niv, minim, tata);
            minim[start] = min(minim[start], minim[nod]);
            if(tata[start] == -1 && child > 1)
            {
                critic[start] = true;
                set<int> aux;
                while(sol.top().first != start && sol.top().second != nod)
                {
                    //cout<<sol.top().first<<" "<<sol.top().second<<"---";
                    aux.insert(sol.top().first);
                    aux.insert(sol.top().second);
                    sol.pop();
                }
                //cout<<sol.top().first<<" "<<sol.top().second<<endl;
                aux.insert(sol.top().first);
                aux.insert(sol.top().second);
                sol.pop();
                comp.push_back(aux);
                aux.clear();
            }
            if(tata[start] != -1 && minim[nod] >= niv[start])
            {
                critic[start] = true;
                set<int> aux;
                while(sol.top().first != start && sol.top().second != nod)
                {
                    //cout<<sol.top().first<<" "<<sol.top().second<<"---";
                    aux.insert(sol.top().first);
                    aux.insert(sol.top().second);
                    sol.pop();
                }
                //cout<<sol.top().first<<" "<<sol.top().second<<endl;
                aux.insert(sol.top().first);
                aux.insert(sol.top().second);
                sol.pop();
                comp.push_back(aux);
                aux.clear();
            }
        }
        else if(nod != tata[start])
        {
            minim[start] = min(minim[start], niv[nod]);
            if(niv[nod] < niv[start])
                sol.push(make_pair(start, nod));
        }
    }
}

int main()
{
    ifstream in("biconex.in");
    ofstream out("biconex.out");
    int n,m;
    in>>n>>m;
    vector<vector<int> > matrice(n+1, vector<int> (n+1, 0));
    vector<vector<int> > adiacenta(n+1);
    vector<bool> viz(n+1, false);
    vector<int> tata (n+1, -1);
    vector<int> niv (n+1, 0);
    vector<int> minim (n+1, 0);
    vector<bool> critic (n+1, false);
    vector<int> status (n+1,0);
    for(int i=1; i<=m; i++)
    {
        int x,y,c;
        in>>x>>y;
        matrice[x][y] = matrice[y][x] = 1;
        adiacenta[x].push_back(y);
        adiacenta[y].push_back(x);
    }

    punct_critic(1, adiacenta, critic, viz, niv, minim, tata);
    set<int> aux;
    while(!sol.empty())
    {
        aux.insert(sol.top().first);
        aux.insert(sol.top().second);
        sol.pop();
    }
    comp.push_back(aux);
    out<<comp.size()<<endl;
    for(int i=0; i<comp.size(); i++)
    {
        for(int nod : comp[i])
            out<<nod<<" ";
        out<<endl;
    }
}