Cod sursa(job #2668090)

Utilizator anacomoAna-Maria Comorasu anacomo Data 4 noiembrie 2020 14:30:12
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.72 kb
#include <bits/stdc++.h>
using namespace std;

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

vector<vector<int>> adiacente;
vector<int> lowlink, depth;
vector<set<int>> components;
int n, m;
stack<pair<int, int>> stiva;


void component(const pair<int, int> &edge)
{
    pair<int, int> topStack;
    set<int> BC;
    do
    {
        topStack = stiva.top();
        stiva.pop();

        BC.insert(topStack.first);
        BC.insert(topStack.second);

    } while (topStack != edge);
    components.push_back(BC);
}

void DFS(int node, int parent, int d)
{

    depth[node] = lowlink[node] = d;
    for (const int &nei : adiacente[node])
        if (nei != parent)
        {
            if (depth[nei] == 0)
            {
                stiva.push(make_pair(node, nei));
                DFS(nei, node, d + 1);
                lowlink[node] = min(lowlink[node], lowlink[nei]);
                if (lowlink[nei] >= depth[node])
                    component(make_pair(node, nei));
            }
            else
                lowlink[node] = min(lowlink[node], depth[nei]);
        }
}

int main()
{
    fin >> n >> m;

    adiacente.resize(n + 1);
    lowlink.resize(n + 1);
    depth.resize(n + 1);
    components.reserve(n);

    for (int e = 0; e < m; ++e)
    {

        int u, v;
        fin >> u >> v;

        adiacente[u].push_back(v);
        adiacente[v].push_back(u);
    }

    for (int node = 1; node <= n; ++node)
        if (depth[node] == 0)
            DFS(node, 0, 1);

    components.resize(components.size());
    fout << components.size() << '\n';

    for (int c = 0; c < (int)components.size(); ++c)
    {
        for (const int &node : components[c])
            fout << node << ' ';
        fout << '\n';
    }
    return 0;
}