Cod sursa(job #3346339)

Utilizator Ianis_PIMDuca Ianis Ianis_PIM Data 13 martie 2026 11:34:23
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.55 kb
#include <iostream>
#include <vector>
#include <stack>
#include <fstream>
using namespace std;
ifstream fin("biconex.in");
ofstream fout("biconex.out");
vector<vector<int>>adj;
vector<bool>V;
vector<int>nivel;
vector<int>nma;
stack<int>S;
vector<vector<int>>R;
int n,m,cnt=0;
void DFS(int k,int c,int tata)
{
    V[k]=true;
    S.push(k);
    nivel[k]=c;
    nma[k]=c;
    for(auto x:adj[k])
        if(x!=tata)
        {
            if(!V[x])
            {
                DFS(x,c+1,k);
                nma[k]=min(nma[k],nma[x]);
                if(nma[x] >= nivel[k])
                {
                    R.push_back(vector<int>());
                    while(S.top()!=x)
                    {
                        R[cnt].push_back(S.top());
                        S.pop();
                    }
                    R[cnt].push_back(S.top());
                    S.pop();
                    R[cnt].push_back(k);
                    cnt++;
                }
            }
            else
            {
                nma[k]=min(nma[k],nivel[x]);
            }
        }
}
int main()
{
    int x,y;
    fin>>n>>m;
    adj.resize(n+1);
    V.resize(n+1,0);
    nivel.resize(n+1);
    nma.resize(n+1);
    for(int i=1; i<=m; i++)
    {
        fin>>x>>y;
        adj[x].push_back(y);
        adj[y].push_back(x);
    }
    for(int i=1; i<=n; i++)
        if(!V[i])
            DFS(i,0,0);
    fout<<cnt<<endl;
    for(int i=0; i<cnt; i++,fout<<endl)
        for(int j:R[i])
            fout<<j<<" ";
    return 0;
}