Cod sursa(job #2864030)

Utilizator BorodiBorodi Bogdan Borodi Data 7 martie 2022 15:10:22
Problema Componente biconexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.37 kb
#include <iostream>
#include <fstream>
#include <queue>
#include <algorithm>
#define Nmax 300001
#include <vector>
#include <stack>
using namespace std;

ifstream fin("biconex.in");
ofstream fout("biconex.out");

typedef vector <int> VI;

stack <int> S;
int id, n, m, x, y, h;
int Low_Link[Nmax], Id[Nmax];
VI V[Nmax], Ans[Nmax];

void Biconex(int vertex){
    id++;
    S.push(vertex);
    Low_Link[vertex] = Id[vertex] = id;

    for(int new_vertex : V[vertex])
        if(Low_Link[new_vertex] == 0){
            Biconex(new_vertex);
            Low_Link[vertex] = min(Low_Link[vertex], Low_Link[new_vertex]);

            if(Low_Link[new_vertex] >= Id[vertex]){
                Ans[++h].push_back(vertex);
                int x = 0;

                do{
                    x = S.top();
                    Ans[h].push_back(x);
                    S.pop();
                }while(x != new_vertex);
            }
        }
        else Low_Link[vertex] = min(Low_Link[vertex], Id[new_vertex]);
}

int main()
{
    fin >> n >> m;

    for(int i = 1; i <= m; ++i){
        fin >> x >> y;
        V[x].push_back(y);
        V[y].push_back(x);
    }

    Biconex(1);

    for(int i = 1; i <= h; ++i){
        fout << Ans[i].size() << '\n';

        for(int j : Ans[i])
            fout << j << " ";

        fout << "\n";
    }
    return 0;
}