Cod sursa(job #3355647)

Utilizator CheeseEaterHackRoman Alex CheeseEaterHack Data 24 mai 2026 14:21:48
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");

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

void dfs(int nod, int tata)
{
    timer++;
    low[nod]=disc[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)
                    {
                        viz[x]=true;
                        rez[cnt].push_back(x);
                    }
                    if (viz[y]==false)
                    {
                        viz[y]=true;
                        rez[cnt].push_back(y);
                    }
                    if (x==nod and y==u)
                    {
                        break;
                    }
                }
                for (int uu: rez[cnt])
                {
                    viz[uu]=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;
}