Cod sursa(job #3030222)

Utilizator florinrafiliuRafiliu Florin florinrafiliu Data 17 martie 2023 16:01:25
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.51 kb
#include <iostream>
#include <vector>
#include <set>
#include <fstream>

using namespace std;

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

const int maxN = 1e5 + 5;

vector <int> g[maxN];
vector <pair<int,int>> muchii;
set <int> comp[maxN];

int T[maxN], minT[maxN], vizit[maxN];
int timp = 0, CB = 0;

void comp_noua (int node, int to) {
    CB++;
    while(true) {
        int a = muchii.back().first, b = muchii.back(). second;
        muchii.pop_back();
        comp[CB].insert(a);
        comp[CB].insert(b);
        if(node == a && to == b)
            return ;
    }
}

void dfs (int node, int dad = -1) {
    T[node] = ++timp;
    minT[node] = timp;
    vizit[node] = true;

    for(int to : g[node]) {
        if(to == dad)
            continue;
        if(vizit[to] == true && minT[node] > T[to]) {
            minT[node] = T[to];
        }
        if(vizit[to] == false) {
            muchii.push_back({node, to});
            dfs(to, node);

            minT[node] = min(minT[node], minT[to]);

            if(T[node] <= minT[to]) {
                comp_noua(node, to);
            }
        }
    }
}

signed main() {

    int n, m; fin >> n >> m;

    for(int i = 1; i <= m; i++) {
        int u, v; fin >> u >> v;

        g[u].push_back(v);
        g[v].push_back(u);
    }

    dfs(1);

    fout << CB << '\n';
    for(int i = 1; i <= CB; i++, fout << '\n')
        for(int j : comp[i])
            fout << j << " ";

    return 0;
}