Cod sursa(job #2786597)

Utilizator butasebiButa Gabriel-Sebastian butasebi Data 21 octombrie 2021 11:25:06
Problema Componente biconexe Scor 90
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.62 kb
#include <bits/stdc++.h>
using namespace std;
int n, m, i, x, y, nivel[100005], nivel_min[100005], nr_comp;
struct muchie
{
    int head1;
    int head2;
};
stack <muchie> Steve;
stack <int> Undo;
vector <int> v[100005];
vector <int> bicomp[100005];
bool viz[100005], viz_bicomp[100005];
void Biconex(int x)
{
    viz[x] = true;
    for(int i = 0; i < v[x].size(); i ++)
    {
        int node = v[x][i];
        if(viz[node] == false)
        {
            //Setam nivelul nodului nou gasit
            nivel[node] = nivel[x] + 1;
            nivel_min[node] = nivel[node];

            //Adaugam o muchie noua in stiva de muchii
            muchie aux;
            aux.head1 = x;
            aux.head2 = node;
            Steve.push(aux);

            //DFS
            Biconex(node);

            //Actualizare nivel minim
            nivel_min[x] = min(nivel_min[x], nivel_min[node]);

            //Verificare punct critic
            if(nivel[x] <= nivel_min[node])
            {
                nr_comp ++;
                muchie aux1 = Steve.top();
                while(!Steve.empty())
                {
                    if(viz_bicomp[aux1.head1] == false)bicomp[nr_comp].push_back(aux1.head1), viz_bicomp[aux1.head1] = true, Undo.push(aux1.head1);
                    if(viz_bicomp[aux1.head2] == false)bicomp[nr_comp].push_back(aux1.head2), viz_bicomp[aux1.head2] = true, Undo.push(aux1.head2);
                    Steve.pop();
                    if((aux1.head1 == x && aux1.head2 == node)|| (aux1.head1 == node && aux1.head2 == x))break;
                    aux1 = Steve.top();
                }
            }
            while(!Undo.empty())
            {
                viz_bicomp[Undo.top()] = false;
                Undo.pop();
            }
        }
        else if(nivel[node] < nivel[x] - 1)
            {
                nivel_min[x] = min(nivel_min[x], nivel_min[node]);

                muchie aux;
                aux.head1 = node;
                aux.head2 = x;
                Steve.push(aux);
            }
    }
}
int main()
{
    ifstream f("biconex.in");
    ofstream g("biconex.out");
    f >> n >> m;
    for(i = 1; i <= m; i ++)
    {
        f >> x >> y;
        v[x].push_back(y);
        v[y].push_back(x);
    }
    nivel[1] = 1;
    nivel_min[1] = 1;
    Biconex(1);
    g << nr_comp << "\n";
    for(i = 1; i <= nr_comp; i ++)
        {
            for(int j = 0; j < bicomp[i].size(); j ++)
                g << bicomp[i][j] << " ";
            g << "\n";
        }
    return 0;
}
/*
8 10
1 2
1 7
2 6
2 7
3 4
3 5
3 6
4 5
5 6
7 8
*/