Cod sursa(job #3311347)

Utilizator Dia3141Costea Diana Stefania Dia3141 Data 21 septembrie 2025 13:43:17
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.9 kb
#include <fstream>
#include <vector>
#include <stack>
#define nmax (int)(1e5+1)
#define inf 1e9
using namespace std;
ifstream cin("biconex.in");
ofstream cout("biconex.out");
int n,m,x,y,niv[nmax],minlv[nmax],total;
bool viz[nmax],pct[nmax];
vector<int>v[nmax],aux;
vector<pair<int,int>>punte;
vector<vector<int>>c;
stack<int>s;
void dfs(int nod,int t){
    niv[nod]=minlv[nod]=niv[t]+1;
    viz[nod]=1;
    s.push(nod);
    int fii=0;
    for(auto i:v[nod])
        if(!viz[i]){
            fii++;
            dfs(i,nod);
            minlv[nod]=min(minlv[nod],minlv[i]);
            if(minlv[i]>=niv[nod]){
                if(!pct[nod]&&nod!=1){
                    total++;
                    pct[nod]=1;
                }
                if(minlv[i]>niv[nod])
                    punte.push_back({nod,i});
                aux.clear();
                while(!s.empty()&&s.top()!=i){
                    aux.push_back(s.top());
                    s.pop();
                }
                aux.push_back(i);
                aux.push_back(nod);
                s.pop();
                c.push_back(aux);
            }
        }else if(i!=t)
            minlv[nod]=min(minlv[nod],niv[i]);
    if(nod==1&&fii>1){
        pct[1]=1;
        total++;
    }
}
int main()
{
    int task=1;
    //cin>>task;
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        cin>>x>>y;
        v[x].push_back(y);
        v[y].push_back(x);
    }
    dfs(1,0);
    if(task==1){
        cout<<c.size()<<'\n';
        for(auto i:c){
            for(auto j:i)
                cout<<j<<" ";
            cout<<'\n';
        }
    }else if(task==2){
        cout<<total<<'\n';
        for(int i=1;i<=n;i++)
            if(pct[i])
                cout<<i<<" ";
    }else{
        cout<<punte.size()<<" ";
        for(auto i:punte)
            cout<<i.first<<" "<<i.second<<'\n';
    }
    return 0;
}