Cod sursa(job #3181042)

Utilizator andreigspdAndrei Gospodaru andreigspd Data 6 decembrie 2023 12:54:14
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.11 kb
#include <bits/stdc++.h>
using namespace std;
ifstream fin("biconex.in");
ofstream fout("biconex.out");
int nrcmp,cnt,n,m,x,y,dfn[100001],low[100001],dad[100001];
vector<int>g[200001];
stack<int>s;
vector<vector<int> >copie;
void biconex(int u,int tata){
 dfn[u]=low[u]=++cnt;
 dad[u]=tata;
 s.push(u);
 for(int x:g[u]){
    if(dfn[x]==0){
        biconex(x,u);
        low[u]=min(low[u],low[x]);
        if(low[x]>=dfn[u]){
            nrcmp++;
            vector<int>linie;
            while(s.top()!=x){
                linie.push_back(s.top());
                s.pop();
            }
            int var=s.top();
            linie.push_back(s.top());s.pop();
            linie.push_back(dad[var]);
            copie.push_back(linie);
        }
    }
    else{
        if(x!=tata)low[u]=min(low[u],dfn[x]);
    }
 }
}
int main(){
  fin>>n>>m;
  for(int i=1;i<=m;i++){
    fin>>x>>y;
    g[x].push_back(y);
    g[y].push_back(x);
  }
  biconex(1,0);
  fout<<nrcmp<<'\n';
  for(int i=0;i<nrcmp;i++){
    for(int j=0;j<copie[i].size();j++)fout<<copie[i][j]<<' ';
    fout<<'\n';
  }
}