Cod sursa(job #2517454)

Utilizator Rares31100Popa Rares Rares31100 Data 3 ianuarie 2020 16:33:12
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.44 kb
#include <bits/stdc++.h>
 
using namespace std;
 
ifstream in("biconex.in");
ofstream out("biconex.out");
 
int n,m;
int vf[400001],urm[400001],last[100001],nrg;
 
int nivel[100001],minNivel[100001];
bitset <100001> viz;
int coada[100001],nrc;
vector <int> sol[100001];
int nrs;
 
void adauga(int nod,int vec)
{
    vf[++nrg]=vec;
    urm[nrg]=last[nod];
    last[nod]=nrg;
}
 
void dfsBic(int nod,int from,int niv=1)
{
    viz[nod]=1;
    nivel[nod]=niv;
    minNivel[nod]=niv;
    coada[++nrc]=nod;
    
    for(int k=last[nod];k;k=urm[k])
        if(vf[k]!=from && viz[ vf[k] ])
            minNivel[nod]=min(minNivel[nod],nivel[ vf[k] ]);
        else if(vf[k]!=from)
        {
            dfsBic(vf[k],nod,niv+1);
            minNivel[nod]=min(minNivel[nod],minNivel[ vf[k] ]);
            
            if(nivel[ nod ]<=minNivel[ vf[k] ])
            {
                nrs++;
                while(coada[nrc]!=vf[k])
                    sol[nrs].push_back(coada[nrc--]);
                    
                sol[nrs].push_back(coada[nrc--]);
                sol[nrs].push_back(nod);
            }
        }
}
 
int main()
{
    in>>n>>m;
    
    for(int i,j,k=1;k<=m;k++)
    {
        in>>i>>j;
        
        adauga(i,j);
        adauga(j,i);
    }
    
    dfsBic(1,0);
    
    out<<nrs<<'\n';
    
    for(int i=1;i<=nrs;i++)
    {
        for(int j=0;j<sol[i].size();j++)
            out<<sol[i][j]<<' ';
            
        out<<'\n';
    }
    
    return 0;
}