Cod sursa(job #3152671)

Utilizator Paul281881818818181991919191881818Draghici Paul Paul281881818818181991919191881818 Data 26 septembrie 2023 10:42:45
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.99 kb
#include <fstream>
#include <iostream>
#include <vector>
#include <stack>
#include <unordered_set>
std::ifstream fin("biconex.in");
std::ofstream fout("biconex.out");
std::vector<std::vector<int>> V;
std::vector<int> dist, low, viz;
std::vector<std::unordered_set<int>> res;
std::stack<int> S;
int cnt;
void AP(int u, int parent, int time){
    viz[u] = true;
    dist[u] = low[u] = ++time;
    int children = 0;
    for(int v : V[u]){
        if(!viz[v]){
            ++children; S.push(u);
            AP(v, u, time);
            low[u] = std::min(low[u], low[v]);
            if(dist[u] == 1 || (dist[u] > 1 && dist[u] <= low[v])){
                S.push(v);
                std::unordered_set<int> values;
                while(!S.empty() && S.top() != u){
                    values.insert(S.top());
                    S.pop();
                }
                if(!S.empty()){
                    values.insert(S.top());
                    S.pop();
                }
                res.push_back(values);
                cnt ++;
            }
        }
        else if(v != parent){
            low[u] = std::min(low[u], dist[v]);
            if(dist[v] < dist[u])
                S.push(u);
        }
    }
}
void APutil(int n){
    dist = low = viz = std::vector<int> (n + 1);
    for(int i = 1; i <= n; i++){
        if(!viz[i]){
            AP(i, -1, 0);
        }
    }
    if(!S.empty())
        ++cnt;
    std::unordered_set<int> temp;
    while(!S.empty()){
        temp.insert(S.top());
        S.pop();
    }
    res.push_back(temp);
    fout << cnt << "\n";
    for(int i = 0; i < res.size(); i++){
        for(auto it : res[i])
            fout << it << " ";
        fout << "\n";
    }
}
int main()
{
    int n, m, x, y;
    fin >> n >> m;
    V = std::vector<std::vector<int>> (n + 1);
    for(int i = 1; i <= m; i++){
        fin >> x >> y;
        V[x].push_back(y);
        V[y].push_back(x);
    }
    APutil(n);
    return 0;
}