Cod sursa(job #2811672)

Utilizator Tudor_PascaTudor Pasca Tudor_Pasca Data 2 decembrie 2021 20:50:58
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.53 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
#include <cstring>
#include <set>

using namespace std;

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

const int INF = 2e9;

int n, m, cont;
int tin[100005], low[100005];
vector<int> adj[100005];
vector<set<int>> cbc;
stack<pair<int, int>> s;

void addComp(int x, int y)
{
    set<int> comp;
    while(!s.empty() && (s.top().first != x || s.top().second != y))
    {
        comp.insert(s.top().first);
        comp.insert(s.top().second);
        s.pop();
    }
    comp.insert(s.top().first);
    comp.insert(s.top().second);
    s.pop();
    cbc.push_back(comp);
}

void dfs(int node, int father = 0)
{
    tin[node] = low[node] = ++cont;

    for(auto it: adj[node])
    {
        if(node == father)
            continue;

        if(tin[it] != 0)
            low[node] = min(low[node], tin[it]);
        else
        {
            s.push({node, it});
            dfs(it, node);
            low[node] = min(low[node], low[it]);
            if(low[it] >= tin[node])
                addComp(node, it);
        }
    }
}

int main()
{
    in >> n >> m;
    for(int i = 1; i <= m; i++)
    {
        int x, y;
        in >> x >> y;
        adj[x].push_back(y);
        adj[y].push_back(x);
    }

    memset(tin, INF, sizeof tin);
    dfs(1);

    out << cbc.size() << '\n';
    for(auto it: cbc)
    {
        for(auto it2: it)
            out << it2 << ' ';
        out << '\n';
    }

    return 0;
}