Cod sursa(job #2470535)

Utilizator uvIanisUrsu Ianis Vlad uvIanis Data 9 octombrie 2019 13:48:01
Problema Componente biconexe Scor 90
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.45 kb
#include <bits/stdc++.h>
using namespace std;

stack<size_t> nodeStack;
vector<vector<size_t>> graph(100001, vector<size_t>());
vector<vector<size_t>> bks;


size_t id[100001], lv[100001], N, M;


void dfs(size_t node, size_t parent)
{
    id[node] = lv[node] = id[parent] + 1;

    nodeStack.push(node);

    for(auto& next : graph[node])
    {
        if(!id[next])
        {
            dfs(next, node);

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

            if(id[node] <= lv[next])
            {
                vector<size_t> bk;

                bk.push_back(node);
                bk.push_back(next);

                while(nodeStack.top() != next)
                {
                    bk.push_back(nodeStack.top());
                    nodeStack.pop();
                }

                nodeStack.pop();

                bks.push_back(bk);
            }
        } else if(next != parent) lv[node] = min(lv[node], id[next]);
    }
}


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

    fin >> N >> M;

    size_t x, y;

    for(; M; M--)
    {
        fin >> x >> y;

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

    for(size_t i = 1; i <= N; ++i)
    {
        if(!id[i]) dfs(i, 0);
    }

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

    for(auto& bk : bks)
    {
        for(auto& node : bk) fout << node << ' ';
        fout << '\n';
    }
}