Cod sursa(job #3263483)

Utilizator AndreiNicolaescuEric Paturan AndreiNicolaescu Data 14 decembrie 2024 14:27:27
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.64 kb
#include <fstream>
#include <vector>
#include <stack>
#include <set>
using namespace std;
ifstream cin("biconex.in");
ofstream cout("biconex.out");
int n, m, x, y, timer;
vector<vector<int>> graf;
vector<int> tin, low, viz;
stack<pair<int, int>> s;

vector<set<int>> comp;
void bicon(int node1, int node2)
{
    set<int> bic;
    int tn1 = -1, tn2 = -1;
    while(tn1 != node1 || tn2 != node2)
    {
        tn1 = s.top().first;
        tn2 = s.top().second;
        s.pop();
        bic.insert(tn1);
        bic.insert(tn2);
    }
    comp.push_back(bic);
}
void dfs(int node, int parent)
{
    viz[node] = 1;
    low[node] = tin[node] = ++timer;
    for(auto next:graf[node])
    {
        if(next == parent)
            continue;
        if(viz[next])
            low[node] = min(low[node], tin[next]);
        else
            if(!viz[next])
            {
                s.push({node, next});
                dfs(next, node);
                low[node] = min(low[node], low[next]);
                if(low[next] >= tin[node]) //pct de art
                    bicon(node, next);
            }
    }
}
int main()
{
    cin >> n >> m;
    graf.assign(n+1, vector<int>());
    viz.resize(n+1);
    tin.resize(n+1);
    low.resize(n+1);
    for(int i=1; i<=m; i++)
    {
        cin >> x >> y;
        graf[x].push_back(y);
        graf[y].push_back(x);
    }
    for(int i=1; i<=n; i++)
        if(!viz[i])
            dfs(i, 0);
    cout << comp.size() << '\n';
    for(int i=0; i<comp.size(); i++, cout << '\n')
    {
        for(auto node:comp[i])
            cout << node << " ";
    }
    return 0;
}