Cod sursa(job #2470547)

Utilizator uvIanisUrsu Ianis Vlad uvIanis Data 9 octombrie 2019 14:36:45
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.35 kb
#include <bits/stdc++.h>

using namespace std;

vector<vector<int>> graph(100001, vector<int>());
vector<vector<int>> bks(100001, vector<int>());
stack<int> nodeStack;
int id[100001], lv[100001], n, m, nr=0;


void dfs(int node, int parent)
{
    id[node] = lv[node] = id[parent] + 1;   nodeStack.push(node);

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

        if(!id[nb])
        {
            dfs(nb, node);
            lv[node] = min(lv[node], lv[nb]);

            if(id[node] <= lv[nb])
            {
                nr++;
                while(nodeStack.top() != nb)
                {
                    bks[nr].push_back(nodeStack.top());
                    nodeStack.pop();
                }

                bks[nr].push_back(node);
                bks[nr].push_back(nb);

                nodeStack.pop();
            }
        } else lv[node] = min(lv[node], id[nb]);
    }
}

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

    fin >> n >> m;

    int x, y;

    for(; m; --m)
    {
        fin >> x >> y;
        graph[x].push_back(y);
        graph[y].push_back(x);
    }

    dfs(1, 0);

    fout << nr << '\n';

    for(int i = 1; i <= nr; i++)
    {
        for(auto& node : bks[i]) fout << node << ' ';
        fout << '\n';
    }
}