Cod sursa(job #3314033)

Utilizator TomMMMMatei Toma TomMMM Data 7 octombrie 2025 20:05:25
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.02 kb
#include <fstream>
#include <string>
#include <vector>
#include <stack>
#include <algorithm>
#include <iostream>

using namespace std;

const string file = "biconex";
#define fileIn file + ".in"
#define fileOut file + ".out"

int n, m;
vector<vector<int>> G;

void reading(){
    ifstream fin(fileIn);
    fin >> n >> m;

    G.resize(n + 1);
    int x, y;
    for(int i = 1; i <= m; i++){
        fin >> x >> y;
        G[x].push_back(y);
        G[y].push_back(x);
    }
}

const int nMax = 1e5 + 5;

int parent[nMax], dis[nMax], low[nMax], globalTime;
vector<vector<int>> comp;
stack<pair<int, int>> s;

void getGroup(int x, int y){ 
    vector<int> nodes;
    int topX, topY;
    do{
        topX = s.top().first;
        topY = s.top().second;
        s.pop();
        nodes.push_back(topX);
        nodes.push_back(topY);
    }while(topX != x || topY != y);
    comp.push_back(nodes);
}

void dfs(int node){
    dis[node] = low[node] = ++globalTime;
    
    for(int child: G[node]){
        if(parent[node] == child) continue;
        if(dis[child] == 0){
            parent[child] = node;
            s.push({node, child});

            dfs(child);

            low[node] = min(low[node], low[child]);
            if(low[child] >= dis[node])
                getGroup(node, child);
        }else
            low[node] = min(low[node], dis[child]);
    }
}

vector<int> getUniqueValues(vector<int> v){
    if(v.empty()) return v;
    sort(v.begin(), v.end());

    vector<int> aux;
    aux.push_back(v[0]);
    for(int i = 1; i < v.size(); i++)
        if(v[i] != v[i - 1]) aux.push_back(v[i]);
    return aux;
}

int main(){
    reading();
    
    for(int i = 1; i <= n; i++)
        if(dis[i] == 0)dfs(i);

    for(int i = 0; i < comp.size(); i++)
        comp[i] = getUniqueValues(comp[i]); 

    ofstream fout(fileOut);
    fout << comp.size() << '\n';
    for(auto &v: comp){
        for(int x: v) 
            fout << x << ' ';
        fout << '\n';
    }
}