Cod sursa(job #2805898)

Utilizator robee1Chitu Robert-Alexandru robee1 Data 22 noiembrie 2021 08:02:07
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.46 kb
#include<iostream>
#include<fstream>
#include<vector>
#include<stack>
using namespace std;
ifstream f("biconex.in");
ofstream g("biconex.out");
stack<int>stiva;
int verif[100002],low[100002],cost[100002];
int n,m,cont=0;
vector<int> muchii[100002],componente[100002];
void biconexe(int nod,int parent){
verif[nod]=true;
low[nod]=cost[nod]=cost[parent]+1;
stiva.push(nod);
for (int i=0;i<muchii[nod].size();i++){
    if (muchii[nod][i] != parent){
        if (verif[muchii[nod][i]])
            low[nod]=min(low[nod],cost[muchii[nod][i]]);
        else{
            biconexe(muchii[nod][i],nod);
            low[nod]=min(low[nod],low[muchii[nod][i]]);
            if (low[muchii[nod][i]]>=cost[nod]){
                cont++;
                while (stiva.top()!=muchii[nod][i]){componente[cont].push_back(stiva.top());stiva.pop();}
                componente[cont].push_back(muchii[nod][i]);stiva.pop();componente[cont].push_back(nod);
            }
        }
    }
}
}
int main() {

    f>>n>>m;
    int x,y;
    for(int i=1;i<=m;i++){
        f>>x>>y;
        muchii[x].push_back(y);
        muchii[y].push_back(x);
    }
    for (int i=1;i<=n;i++)
        if (verif[i]==0)
            biconexe(i,0);
    g<<cont<<'\n';
    for (int i=1;i<=cont;i++){
        for (int j=componente[i].size()-1;j>=0;j--)
            g<< componente[i][j]<<" ";
        g<<'\n';
    }
 /*   for(int i=1;i<=n;i++){
        cout<<low[i];
    } */
    return 0;
}