Cod sursa(job #2489588)

Utilizator uvIanisUrsu Ianis Vlad uvIanis Data 9 noiembrie 2019 08:27:38
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.39 kb
#include <bits/stdc++.h>
#define NMAX 100001
using namespace std;

ifstream fin{"biconex.in"};
ofstream fout{"biconex.out"};

vector<vector<int>> graph(NMAX, vector<int>());
int N, M;

int id[NMAX], low[NMAX];
stack<int> s;

int _time = 0;

vector<vector<int>> bcs;

void biconnected(int node, int parent)
{
    id[node] = low[node] = ++_time;
    s.push(node);

    for(auto& next : graph[node])
    {
        if(next == parent) continue;

        if(id[next] == 0)
        {
            biconnected(next, node);

            low[node] = min(low[node], low[next]);

            if(low[next] >= id[node])
            {
                bcs.push_back(vector<int>());
                int x;

                do
                {
                    x = s.top();
                    bcs.back().push_back(x);
                    s.pop();
                }
                while(x != next);

                bcs.back().push_back(node);
            }
        }
        else low[node] = min(low[node], id[next]);
    }
}


int main()
{
    fin >> N >> M;

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

    biconnected(1, -1);

    fout << bcs.size() << '\n';

    for(auto& bc : bcs)
    {
        for(auto& node : bc) fout << node << ' ';
        fout << '\n';
    }
}