Cod sursa(job #2698920)

Utilizator SoranaAureliaCatrina Sorana SoranaAurelia Data 23 ianuarie 2021 11:25:25
Problema Componente biconexe Scor 90
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.88 kb
#include <fstream>
#include <algorithm>
#include <iostream>
#include <vector>
#include <stack>
#define NMAX 100005
using namespace std;

ifstream f("biconex.in");
ofstream g("biconex.out");

int n, m;
int index[NMAX], lowlink[NMAX];
int viz[NMAX], idx=1;
int nr_componente;

vector<int>graph[NMAX];
vector<vector<int>> sol;
stack<pair<int, int>>S; // nodurile

void citire(){
    f>>n>>m;
    int x, y;
    for(int i=0; i<m; i++){
        f>>x>>y;
        graph[x].push_back(y);
        graph[y].push_back(x);
    }
}

void biconex(int nod, int parent){
    index[nod] = idx;
    lowlink[nod] = idx;
    idx++;

    viz[nod] = 1;


    for(auto &v:graph[nod]){
        if(v == parent)
            continue;
        if(viz[v] == 0){
            S.push({nod, v});
            biconex(v, nod);
            lowlink[nod] = min(lowlink[v], lowlink[nod]);

            if(lowlink[v] >= index[nod]){
                nr_componente++;
                pair<int, int> el;
                vector<int> temp;
                do{
                    el = S.top();
                    temp.push_back(el.first);
                    temp.push_back(el.second);
                    S.pop();
                }while(el.first != nod && el.second != v);

                sort(temp.begin(), temp.end());
                temp.erase(unique(temp.begin(), temp.end()), temp.end());
                sol.push_back(temp);
            }

        }
        else{
            lowlink[nod] = min(lowlink[v], lowlink[nod]);
        }
    }


}

void parcurgere(){
    biconex(1, 0);
}

void afisare(){
    g<<nr_componente<<'\n';
    for(auto &c:sol){
        for(auto v: c)
            g<<v<<' ';
        g<<'\n';
    }
}
int main()
{
    citire();
    parcurgere();
    /**for(int i=1; i<=n; i++){
        cout<<lowlink[i]<<' ';
    }**/
    afisare();
    return 0;
}