Cod sursa(job #3295203)

Utilizator BucsMateMate Bucs BucsMate Data 3 mai 2025 15:52:12
Problema Componente biconexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.37 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>

using namespace std;

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

stack<pair<int, int>> st;
int time = 1;
vector<vector<int>> megoldas;

const int INF = 1000*1000*1000;


void DFS(vector<vector<int>> &adj, int node, vector<int> &low, vector<int> &disc, vector<int> &parent, vector<vector<int>> &adj_new)
{
    disc[node] = time;
    low[node] = time;
    time++;
    int children = 0;


    for(int i = 0; i < adj[node].size(); i++){
        int newNode = adj[node][i];

        if(disc[newNode] == INF){
            children++;
            parent[newNode] = node;
            st.push({node, newNode});
            DFS(adj, newNode, low, disc, parent, adj_new);
            low[node] = min(low[node], low[newNode]);
            if((disc[node] == 1 && children > 1) || disc[node] > 1 && low[newNode] >= disc[node]){
                pair<int, int> curr = st.top();
                st.pop();
                adj_new[curr.first].push_back(curr.second);
                adj_new[curr.second].push_back(curr.first);
                while(curr.first != node && curr.second != newNode){
                    curr = st.top();
                    st.pop();
                    adj_new[curr.first].push_back(curr.second);
                    adj_new[curr.second].push_back(curr.first);
                }

            }
        }
        else if(newNode != parent[node]){
            low[node] = min(low[node], disc[newNode]);
            if (disc[newNode] < disc[node]) {
                st.push({node, newNode});
            }
        }
    }
}

int main()
{
    int N, M;
    fin >> N >> M;
    vector<vector<int>> adj(N+1), adj_new(N+1);

    for(int i = 0; i < M; i++){
        int a, b;
        fin >> a >> b;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }

    vector<int> disc(N+1, INF);
    vector<int> low(N+1, INF);
    vector<int> parent(N+1, -1);
    for(int i = 1; i <= N; i++){
        time = 1;
        if(disc[i] == INF){
            DFS(adj, i, low, disc, parent, adj_new);
        }
    }


    fout << megoldas.size() << endl;
    for(int i = 0; i < megoldas.size(); i++){
        for(int j = 0; j < megoldas[i].size(); j++){
            fout << megoldas[i][j] << " ";
        }
        fout << endl;
    }
    return 0;
}