Cod sursa(job #3275191)

Utilizator AlexandraVarutuValexandra AlexandraVarutu Data 9 februarie 2025 13:52:47
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.12 kb
#include <fstream>
#include <vector>
#include <stack>
using namespace std;
ifstream fin("biconex.in");
ofstream fout("biconex.out");
//componentebiconexe
//biconex
int n,m,niv[100001],minlv[100001],nr,pct;
bool artic[100001],viz[100001];
struct punte{
  int x,y;
}punte[50001];
vector<int>v[100001],ccb[100001];
stack<int>sol;
void dfs(int k, int tata){
    viz[k]=1;
    sol.push(k);
    niv[k]=minlv[k]=niv[tata]+1;
    int fii=0;
    for(auto i:v[k]){
        if(viz[i]==1){
          if(i!=tata)  /// am muchie de intoarcere
             minlv[k]=min(minlv[k],niv[i]);
        }
        else{
            fii++;
            dfs(i,k);
            minlv[k]=min(minlv[k],minlv[i]);
            if(niv[k]<=minlv[i]){
                if(k!=1) /// pct de articulatie
                      artic[k]=1;
                 nr++;/// imi da comp biconexe
                    while(sol. top()!=i){
                        ccb[nr].push_back(sol. top());
                        sol.pop();
                    }
                    ccb[nr].push_back(i);
                    sol.pop();
                    ccb[nr].push_back(k);
            }
            if(niv[k]<minlv[i]) { /// k i punte
                punte[++pct]={k,i};
            }
        }

    }
    if(k==1&&fii>=2)
          artic[k]=1;
}
int main()
{
    int p;
  //  fin>>p;
  p=1;
    fin>>n>>m;
    int x,y;
    for(int i=1;i<=m;i++){
        fin>>x>>y;
        v[x].push_back(y);
        v[y].push_back(x);
    }
    dfs(1,0);
    if(p==1){
        fout<<nr<<'\n';
        for(int i=1;i<=nr;i++){
          ///  fout<<ccb[i].size()<<" ";
            for(auto j:ccb[i])
                fout<<j<<" ";
            fout<<'\n';
        }
        return 0;
    }
    if(p==2){
        int nr=0;
        for(int i=1;i<=n;i++)
              if(artic[i])
                 nr++;
        fout<<nr<<"\n";
        for(int i=1;i<=n;i++)
             if(artic[i]==1)
                 fout<<i<<" ";
       return 0;
    }

    fout<<pct<<"\n";
    for(int i=1;i<=pct;i++){
        fout<<punte[i].x<<" "<<punte[i].y<<'\n';
    }
    return 0;
}