Cod sursa(job #3346348)

Utilizator CheeseEaterHackRoman Alex CheeseEaterHack Data 13 martie 2026 12:11:42
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.01 kb
#include <bits/stdc++.h>
using namespace std;
ifstream fin("biconex.in");
ofstream fout("biconex.out");

int n, m, low[100001], disc[100001], a, b;
vector<int> graf[100001], rez[100001];
stack<pair<int, int>> st;
int timer, cnt;
bool viz[100001];

void dfs(int nod, int tata)
{
    timer++;
    disc[nod]=low[nod]=timer;
    for (int u: graf[nod])
    {
        if (u==tata) continue;
        if (disc[u]==0)
        {
            st.push({nod, u});
            dfs(u, nod);
            low[nod]=min(low[nod], low[u]);
            if (low[u]>=disc[nod])
            {
                cnt++;
                while(true)
                {
                    int x=st.top().first;
                    int y=st.top().second;
                    st.pop();
                    if (viz[x]==false)
                    {
                        rez[cnt].push_back(x);
                        viz[x]=true;
                    }
                    if (viz[y]==false)
                    {
                        rez[cnt].push_back(y);
                        viz[y]=true;
                    }
                    if (x==nod and y==u)
                    {
                        break;
                    }
                }
                for (int xx:rez[cnt])
                {
                    viz[xx]=false;
                }
            }

        }
        else if (disc[u]<disc[nod])
        {
            st.push({nod, u});
            low[nod]=min(low[nod], disc[u]);
        }
    }
}

int main()
{
    fin>>n>>m;
    for (int i=1; i<=m; i++)
    {
        fin>>a>>b;
        graf[a].push_back(b);
        graf[b].push_back(a);
    }
    for (int i=1; i<=n; i++)
    {
        if (disc[i]==0)
        {
            dfs(i, 0);
        }
    }
    fout<<cnt<<'\n';
    for (int i=1; i<=cnt; i++)
    {
        sort(rez[i].begin(), rez[i].end());
        for (int u:rez[i])
        {
            fout<<u<<" ";
        }
        fout<<'\n';
    }

    return 0;
}