Cod sursa(job #2805882)

Utilizator robee1Chitu Robert-Alexandru robee1 Data 22 noiembrie 2021 04:28:18
Problema Componente biconexe Scor 28
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.99 kb
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
ifstream f("biconex.in");
ofstream g("biconex.out");
vector <int> muchii[100001];
bool verif[100001];
bool verif2[100001];
vector <int> cost(100001, 0);
vector <int> low(100001, 0);
vector <int> parent(100001, 5555555);
vector <int> articulatii;
vector <int> noduri;
int n,m,x,y, cont, timp,u=-1;
void AP(int v){
    verif[v]=true;
    timp++;
    low[v]=timp;
    cost[v]=timp;
    int child=0;

    for (int i=0; i<muchii[v].size();i++){
            if(!verif[muchii[v][i]]){
                child++;
                parent[muchii[v][i]]=v;
                AP(muchii[v][i]);
                low[v]= min(low[v],low[muchii[v][i]]);
                if (parent[v]==5555555 && child > 1){
                    cont++; articulatii.push_back(v);}
                if(parent[v]!=5555555 && low[muchii[v][i]] >= cost[v]){
                    cont++; articulatii.push_back(v);}

            }
            else if (muchii[v][i] != parent[v])
                low[v] = min(low[v], cost[muchii[v][i]]);

        }

}
void conex(int nod){
    verif2[nod]=true;
    if (u==-1){
        for (int i=0; i<articulatii.size();i++){
            if (nod==articulatii[i])
                u=nod;
        }
    }
    cout<<u<<" ";
    noduri.push_back(nod);
    for (int i=0; i<muchii[nod].size();i++){
        int vecin = muchii[nod][i];
        for (int j = 0; j<articulatii.size();j++){
            if (articulatii[j]==vecin && vecin!= parent[vecin]){
                for (int k=0; k<noduri.size();k++){
                    g<<noduri[k]<<" ";
                }
                g<<'\n';noduri.clear();u=articulatii[j];
            }
        }
        if(!verif2[vecin])
            conex(vecin);

    }

}

int main()
{
    f>>n>>m;
for (int i=1; i<=m;i++)
    {
        f>>x>>y;
        muchii[x].push_back(y);
        muchii[y].push_back(x);
    }


AP(1);
g<<cont+1<<'\n';
conex(1);

    return 0;
}