Cod sursa(job #3370437)

Utilizator viflaem2Granat Andrei Ionut viflaem2 Data 26 octombrie 2026 11:24:20
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.47 kb
#include <bits/stdc++.h>

using namespace std;
vector<vector<int>> graf(100001);
vector<int> ordine(100001);
vector<int> low(100001);
vector<set<int>> componente;
vector<pair<int,int>> muchii;
int n,m,o=1,indice=-1;
ifstream f("biconex.in");
ofstream g("biconex.out");
void DFS(int nod,int parinte){
    ordine[nod]=o; low[nod]=o; o++;
    for(int i=0;i<graf[nod].size();i++){
        int v=graf[nod][i];
        if(!ordine[v]){
            muchii.push_back({nod,v});
            DFS(v,nod);
            if(low[v]<low[nod])
                low[nod]=low[v];
            if(low[v]>=ordine[nod]){
                indice++;
                componente.emplace_back();
                int x,y;
                do{
                    x=muchii.back().first; y=muchii.back().second;
                    componente[indice].insert(x); componente[indice].insert(y);
                    muchii.pop_back();
                }while(x!=nod||y!=v);
            }
        }
        else if(ordine[v]<ordine[nod]&&v!=parinte){
            muchii.push_back({nod,v});
            if(ordine[v]<low[nod])
                low[nod]=ordine[v];
        }
    }
}
int main()
{
f>>n>>m;
for(int i=0;i<m;i++){
    int x,y; f>>x>>y;
    graf[x].push_back(y);
    graf[y].push_back(x);
}
for(int i=1;i<=n;i++){
    if(!ordine[i])
        DFS(i,0);
}
g<<indice+1<<endl;
for(int i=0;i<=indice;i++){
    for(int nod:componente[i])
        g<<nod<<" ";
    g<<endl;
}
return 0;
}