Cod sursa(job #2869076)

Utilizator MateiAruxandeiMateiStefan MateiAruxandei Data 11 martie 2022 12:23:09
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.44 kb
#include <bits/stdc++.h>

using namespace std;

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

using ll = long long;
const int NMAX(100005);
vector<int> G[NMAX], comp[NMAX];
int cnt, low[NMAX], dfn[NMAX];
stack<int> st;

inline void addComp(int fis)
{
    while(st.top() != fis)
    {
        comp[cnt].push_back(st.top());
        st.pop();
    }
    comp[cnt].push_back(st.top());
    st.pop();
}

inline void biconex(int nod, int dist)
{
    low[nod] = dfn[nod] = dist;
    st.push(nod);
    for(auto it: G[nod])
        if(dfn[it] == -1)
        {
            biconex(it, dist + 1);
            low[nod] = min(low[nod], low[it]);
            if(dfn[nod] <= low[it])
            {
                ++cnt;
                if(st.size() > 0)
                    addComp(it);
                comp[cnt].push_back(nod);
            }
        }
        else low[nod] = min(low[nod], dfn[it]);
}

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

    for(int i = 1; i <= m; ++i)
    {
        int x, y;
        fin >> x >> y;
        G[x].push_back(y);
        G[y].push_back(x);
    }

    for(int i = 1; i <= n; ++i)
        dfn[i] = low[i] = -1;
    for(int i = 1; i <= n; ++i)
        if(dfn[i] == -1)
            biconex(i, 0);

    fout << cnt << '\n';
    for(int i = 1; i <= cnt; ++i)
    {
        for(auto it: comp[i])
            fout << it << ' ';
        fout << '\n';
    }
    return 0;
}