Cod sursa(job #2505025)

Utilizator VladG26Ene Vlad-Mihai VladG26 Data 6 decembrie 2019 02:15:34
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.01 kb
#include <iostream>
#include <bits/stdc++.h>

#define in_file "biconex.in"
#define out_file "biconex.out"
#define NMAX 100005
#define INF 1000003

using namespace std;
vector<int> G[NMAX];
vector<vector<int>> biconex_comp;
vector<bool> viz;
vector<int> lvl;
vector<int> min_achievable_lvl;
stack<pair<int, int>> edge;

void printVec(vector<int> v){
    for(auto e : v){
        fprintf(stdout, "%d, ", e);
    }
}

void dfs(int node,int cameFrom){
    viz[node]=true;

    for(auto n:G[node]){

        //if(n==cameFrom) continue;

        if(!viz[n]){

            edge.push({node, n});

            min_achievable_lvl[n]=lvl[n]=lvl[node]+1;

            dfs(n, node);

            min_achievable_lvl[node]=min(min_achievable_lvl[n],min_achievable_lvl[node]);

            if(min_achievable_lvl[n]>=lvl[node]){

                vector<int> nodes;

                while(edge.top().first != node){
                    nodes.push_back(edge.top().second);
                    edge.pop();
                }

                nodes.push_back(edge.top().second);
                nodes.push_back(edge.top().first);

                edge.pop();

                biconex_comp.push_back(nodes);
            }
        }
        else{
            min_achievable_lvl[node]=min(min_achievable_lvl[node], lvl[n]);
        }
    }
}

int main()
{
    freopen(in_file, "r", stdin);
    freopen(out_file, "w", stdout);
    int n,m;
    cin>>n>>m;
    int n1, n2;
    while(m--){
        cin>>n1>>n2;
        G[n1].push_back(n2);
        G[n2].push_back(n1);
    }
    viz=vector<bool>(n+1, false);
    lvl=vector<int>(n+1);
    min_achievable_lvl=vector<int>(n+1, INF);
    min_achievable_lvl[0]=0;
    lvl[0]=0;
    for(int i=1; i<=n; i++){
        if(!viz[i]){
            dfs(i, 0);
        }
    }


    cout<<biconex_comp.size()<<"\n";
    for(auto comp:biconex_comp){
        for(auto n: comp){
            cout<<n<<" ";
        }
        cout<<"\n";
    }
    return 0;
}