Cod sursa(job #3318951)

Utilizator GabiRB1Rafael GabiRB1 Data 29 octombrie 2025 21:33:04
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.63 kb
#include <bits/stdc++.h>
using namespace std;

vector <int> v[100005];
int low[100005], timp[100005], ct, viz[100005];
deque <pair<int, int>> q;
vector<vector<int>> b;
void new_bix(int x, int y)
{
    vector <int> p;
    unordered_set<int> unic;
    while(q.back().first != x && q.back().second != y)
        unic.insert(q.back().first), unic.insert(q.back().second), q.pop_back();
    unic.insert(q.back().first), unic.insert(q.back().second), q.pop_back();
    for(unordered_set <int> :: iterator i = unic.begin(); i != unic.end(); i ++)
        p.push_back(*i);
    b.push_back(p);
}
void dfs(int k, int p)
{
    int copii = 0;
    viz[k] = 1;
    timp[k] = low[k] = ++ct;
    for(int i = 0; i < v[k].size(); i ++)
    {
        if(viz[v[k][i]] == 0)
        {
            q.push_back({k, v[k][i]});
            copii ++;
            dfs(v[k][i], k);
            low[k] = min(low[k], low[v[k][i]]);
            if(timp[k] <= low[v[k][i]])
                new_bix(k, v[k][i]);
        }
        else if(v[k][i] != p)
            low[k] = min(low[k], timp[v[k][i]]);
    }
}
int main()
{
    int n, m;
    ifstream f("biconex.in");
    ofstream g("biconex.out");
    f >> n >> m;
    for(int i = 1; i <= m; i ++)
    {
        int x, y;
        f >> x >> y;
        v[x].push_back(y);
        v[y].push_back(x);
    }
    for(int i = 1; i <= n; i ++)
        if(viz[i] == 0)
            q.clear(), dfs(i, -1);
    g << b.size() << "\n";
    for(int i = 0; i < b.size(); i ++)
    {
        for(int j = 0; j < b[i].size(); j ++)
            g << b[i][j] << " ";
        g << "\n";
    }
    return 0;
}