Cod sursa(job #2908777)

Utilizator mihneazzzMacovei Daniel mihneazzz Data 5 iunie 2022 20:12:42
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.91 kb
#include <bits/stdc++.h>
#define N 100005
using namespace std;
ifstream fin("biconex.in");
ofstream fout("biconex.out");
int task,n,m,nivel[N],nma[N],nrb,root;
bool viz[N],critic[N];
vector<int>g[N],biconexe[N];
struct muchie
{
    int x,y;
};
vector<muchie>punti;
stack<int>stv;
void DFS(int nod,int tata)
{
    viz[nod]=1;
    stv.push(nod);
    nivel[nod]=nivel[tata]+1;
    nma[nod]=nivel[nod];
    for(auto x:g[nod])
        if(x!=tata)
          if(viz[x]) nma[nod]=min(nma[nod],nivel[x]);
          else
          {
              DFS(x,nod);
              nma[nod]=min(nma[nod],nma[x]);
              if(nivel[nod]<=nma[x] && nod!=root)
                critic[nod]=1;
              if(nivel[nod]<nma[x]) punti.push_back({nod,x});
              if(nivel[nod]<=nma[x])
              {
                  ++nrb;
                  while(stv.top()!=x)
                    biconexe[nrb].push_back(stv.top()),stv.pop();
                  biconexe[nrb].push_back(x);
                  stv.pop();
                  biconexe[nrb].push_back(nod);
              }
          }
}
int main()
{
    int i,j,x,y;
    task=1;
    fin>>n>>m;
    for(i=1;i<=m;i++) fin>>x>>y,g[x].push_back(y),g[y].push_back(x);
    root=1;
    DFS(root,0);
    if(task==1)
    {
        fout<<nrb<<"\n";
        for(i=1;i<=nrb;i++)
        {
            //fout<<biconexe[i].size()<<" ";
            for(auto x:biconexe[i]) fout<<x<<" ";
            fout<<"\n";
        }
    }
    else if(task==2)
    {
        bool ok=0;
        int nrc=0;
        for(i=1;i<=n;i++)
            if(nivel[i]==2)
               if(!ok) ok=1;
               else {critic[1]=1;break;}
        fout<<count(critic+1,critic+n+1,1)<<"\n";
        for(i=1;i<=n;i++)
            if(critic[i]) fout<<i<<" ";
    }
    else
    {
        fout<<punti.size()<<"\n";
        for(auto k:punti) fout<<k.x<<" "<<k.y<<"\n";
    }
    return 0;
}