Cod sursa(job #3374952)

Utilizator ambicepsmareBugeac Alexandru ambicepsmare Data 9 noiembrie 2026 20:10:44
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 3.26 kb

#include <iostream>
#include <fstream>
#include <vector>
#include <stack>

using namespace std;

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

const int NMAX = 100001;
const int MMAX = 200001;

struct Muchie
{
    int nod;
    int id;
};

int n, m;
int dfn[NMAX], low[NMAX];
int tata[NMAX], idTata[NMAX];
int poz[NMAX];
int viz[NMAX];

int x[MMAX], y[MMAX];

vector<Muchie> graf[NMAX];
vector<int> st;
vector<vector<int> > componente;

int timp = 0;

void formeazaComponenta(int id)
{
    vector<int> comp;
    int token = (int)componente.size() + 1;

    while (!st.empty())
    {
        int muchie = st.back();
        st.pop_back();

        if (viz[x[muchie]] != token)
        {
            viz[x[muchie]] = token;
            comp.push_back(x[muchie]);
        }

        if (viz[y[muchie]] != token)
        {
            viz[y[muchie]] = token;
            comp.push_back(y[muchie]);
        }

        if (muchie == id)
            break;
    }

    componente.push_back(comp);
}

void dfs(int start)
{
    stack<int> s;

    timp++;
    dfn[start] = low[start] = timp;
    s.push(start);

    while (!s.empty())
    {
        int nod = s.top();

        if (poz[nod] < (int)graf[nod].size())
        {
            Muchie muchie = graf[nod][poz[nod]];
            poz[nod]++;

            int vecin = muchie.nod;
            int id = muchie.id;

            if (id == idTata[nod])
                continue;

            if (dfn[vecin] == 0)
            {
                tata[vecin] = nod;
                idTata[vecin] = id;

                st.push_back(id);

                timp++;
                dfn[vecin] = low[vecin] = timp;

                s.push(vecin);
            }
            else if (dfn[vecin] < dfn[nod])
            {
                st.push_back(id);

                if (dfn[vecin] < low[nod])
                    low[nod] = dfn[vecin];
            }
        }
        else
        {
            s.pop();

            if (tata[nod] != 0)
            {
                int parinte = tata[nod];

                if (low[nod] < low[parinte])
                    low[parinte] = low[nod];

                if (low[nod] >= dfn[parinte])
                    formeazaComponenta(idTata[nod]);
            }
        }
    }
}

int main()
{
    fin >> n >> m;

    for (int i = 1; i <= m; i++)
    {
        fin >> x[i] >> y[i];

        Muchie a, b;

        a.nod = y[i];
        a.id = i;

        b.nod = x[i];
        b.id = i;

        graf[x[i]].push_back(a);
        graf[y[i]].push_back(b);
    }

    for (int i = 1; i <= n; i++)
    {
        if (dfn[i] == 0)
        {
            if (graf[i].empty())
            {
                vector<int> comp;
                comp.push_back(i);
                componente.push_back(comp);
            }
            else
            {
                dfs(i);
            }
        }
    }

    fout << componente.size() << '\n';

    for (int i = 0; i < (int)componente.size(); i++)
    {
        for (int j = 0; j < (int)componente[i].size(); j++)
            fout << componente[i][j] << " ";

        fout << '\n';
    }

    fin.close();
    fout.close();

    return 0;
}