Cod sursa(job #3364137)

Utilizator nicoleta_iancuIancu Nicoleta nicoleta_iancu Data 30 august 2026 17:24:55
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.9 kb

#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <stack>
#include <algorithm>

using namespace std;

ifstream fin("biconex.in");
ofstream fout("biconex.out");
const int inf = 1e6;
vector<vector<pair<int, int>>>graph;
vector<vector<pair<int, int>>>arb;//arbore cu back-edguri orientat 
vector<pair<int, int>>muchii;
vector<int>minBackEdge;//minBackEdge[i]= nivelul minim la care merge un backedge din subarborele lui i
vector<bool>viz;
vector<bool>viz2;
vector<int>depth; 
void DFS(int nodCrt, int muchieTata, int depthCrt) {
    minBackEdge[nodCrt] = depthCrt;
    depth[nodCrt] = depthCrt;
    viz[nodCrt] = 1;
    for (auto i : graph[nodCrt]) {
        int nod = i.first;
        int muchie = i.second;
        if (muchie != muchieTata) {
            if (viz[nod]) {
                arb[nodCrt].push_back(i);
                minBackEdge[nodCrt] = min(minBackEdge[nodCrt], depth[nod]);
            }
            else {
                arb[nod].push_back(make_pair(nodCrt, muchieTata));
                DFS(nod, muchie, depthCrt + 1);
                minBackEdge[nodCrt] = min(minBackEdge[nodCrt], minBackEdge[nod]);
            }
        }
    }
}
vector<vector<int>>compBi;
stack<int>stackRec;

void calcElemBiconex(int nodCrt) {
    viz2[nodCrt] = 1;
    for (auto i : graph[nodCrt]) {
        int nod = i.first;
        int muchie = i.second;
        if (!viz2[nod]) {
            stackRec.push(muchie);
            calcElemBiconex(nod);
            if (minBackEdge[nod] >= depth[nodCrt]) {
                vector<int>crt;
                int aux;
                do {
                    aux =stackRec.top();
                    crt.push_back(muchii[aux].first);
                    crt.push_back(muchii[aux].second);
                    stackRec.pop();
                } while (aux != muchie);
                sort(crt.begin(), crt.end());
                crt.erase(unique(crt.begin(), crt.end()), crt.end());
                compBi.push_back(crt);
            }
        }
    }
}
int main()
{
    int n, m;
    fin.tie(NULL);
    ios::sync_with_stdio(false);
    fin >> n >> m;
    int u, v;
    graph.resize(n + 1);
    muchii.resize(m);
    for (int i = 0; i < m; ++i) {
        fin >> u >> v;
        graph[u].push_back(make_pair(v, i));
        graph[v].push_back(make_pair(u, i));
        muchii[i] = make_pair(u, v);
    }
    viz.resize(n + 1);
    viz2.resize(n + 1);
    depth.resize(n + 1);
    minBackEdge.resize(n + 1,inf);
    arb.resize(n + 1);
    for (int i = 1; i <= n; ++i) {
        if (!viz[i]) {
            DFS(i, -1, 0);
            calcElemBiconex(i);
            arb.clear();
        }
    }
    fout << compBi.size() << "\n";
    for (int i = 0; i < compBi.size(); ++i) {
        for (auto j : compBi[i]) {
            fout << j << " ";
        }
        fout << "\n";
    }
    return 0;
}
//=^..^=