Cod sursa(job #3323136)

Utilizator preda_alexandraPreda Maria Alexandra preda_alexandra Data 17 noiembrie 2025 11:40:38
Problema Componente biconexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 3.46 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
using namespace std;

ifstream fin ("biconexe.in");
ofstream fout("biconexe.out");

vector<vector<int>> graf;
vector<int> viz;
vector<int> timp;
vector<int> low;
vector<int> tata, art;
stack<pair<int, int>> st;
vector<vector<pair<int, int>>> bicon;

int N, M;

void dfs(int x, int& contor, int& nr)
{
    viz[x] = 1;
    int copii = 0;
    for(auto& i : graf[x])
    {
        if(viz[i] == 0)
        {
            st.push({x, i});
            tata[i] = x;
            copii++; // numar cati copii are nodul curent
            timp[i] = ++contor;
            low[i] = contor;
            dfs(i, contor, nr);
            low[x] = min(low[x], low[i]);
            if(low[i] >= timp[x])
            {
                nr++; // am gasit o componenta biconexa
                bicon.push_back(vector<pair<int,int>>());

                while(!st.empty())
                {
                    pair<int, int> vf = st.top();
                    bicon.back().push_back(vf);
                    st.pop();

                    if ((vf.first == x && vf.second == i) || (vf.first == i && vf.second == x))
                        break;
                }
            }
        }
        else if(tata[x] != i)
        {
            st.push({x, i});
            low[x] = min(low[x], timp[i]);
        }
    }
}



int main()
{
    fin>>N>>M;
    int nr = 0; // nr de compenente biconexe
        graf.assign(N+1, {});  // {} -> graf gol
        viz.assign(N+1, 0);
        timp.assign(N+1, 0);
        low.assign(N+1, 0);
        tata.assign(N+1, 0);
        art.assign(N+1, 0);
        for(int i=1; i<=M; i++)
        {
            int x,y;
            fin>>x>>y;
            graf[x].push_back(y);
            graf[y].push_back(x);
        }
        int contor = 1;

        for(int i=1; i<=N; i++)
            if(viz[i] == 0)
            {
                timp[i] = contor;
                low[i] = contor;
                dfs(i, contor, nr);

            }


        cout << nr << "\n";

for (int j = 0; j < nr; j++)
{
    vector<int> noduri;
    vector<int> apare(N + 1, 0);

    // extrag nodurile fără duplicate
    for (auto &m : bicon[j])
    {
        if (!apare[m.first])
        {
            apare[m.first] = 1;
            noduri.push_back(m.first);
        }
        if (!apare[m.second])
        {
            apare[m.second] = 1;
            noduri.push_back(m.second);
        }
    }

    // afișez nodurile componentei biconexe
    for (int x : noduri)
        cout << x << " ";
    cout << "\n";
}







        /*
        /// aici numaram cate puncte de articulatie am, pt alta problema
        for(int i=1; i<art.size(); i++)
                nr += art[i];

        cout<<nr<<endl;
        */


    return 0;
}


/*void bfs(int x, int& ok)
{
    viz[x] = 1;
    culoare[x] = 1;
    while(!coada.empty())
    {
        for(auto &i : graf[x])
        {
            if(viz[i] == 1)
            {
                if(culoare[x] == culoare[i])
                    ok = 0;
            }
            if(viz[i] == 0)
            {
                viz[i] = 1;
                coada.push(i);
                if(culoare[x] == 1)
                    culoare[i] = 2;
                else culoare[i] = 1;
            }
        }
        coada.pop();
        if(!coada.empty())
            x = coada.front();
    }
}*/