Cod sursa(job #2569484)

Utilizator ursu0406Ursu Ianis-Vlad ursu0406 Data 4 martie 2020 12:19:46
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.48 kb
#include <bits/stdc++.h>

using namespace std;

const int N_MAX = 1e5 + 1;

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

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

int id[N_MAX], low[N_MAX], t;
stack<int> node_stack;
vector<vector<int>> sol;

void dfs_bcc(int node, int parent)
{
    ++t;
    id[node] = t;
    low[node] = t;
    node_stack.push(node);

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

        if(id[next] != 0)
            low[node] = min(low[node], id[next]);
        else
        {
            dfs_bcc(next, node);
            low[node] = min(low[node], low[next]);

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

                while(node_stack.top() != next)
                {
                    sol.back().push_back(node_stack.top());
                    node_stack.pop();
                }

                node_stack.pop();
            }
        }
    }
}


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

    for(int x, y, i = 1; i <= M; ++i)
    {
        fin >> x >> y;

        graph[x].push_back(y);
        graph[y].push_back(x);
    }

    dfs_bcc(1, -1);

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

    for(auto& bcc : sol)
    {
        for(auto& node : bcc)
            fout << node << ' ';

        fout << '\n';
    }
}