Cod sursa(job #2555741)

Utilizator KappaClausUrsu Ianis Vlad KappaClaus Data 24 februarie 2020 11:58:48
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.41 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';
    }
}