Cod sursa(job #2835396)

Utilizator florinrafiliuRafiliu Florin florinrafiliu Data 18 ianuarie 2022 17:32:43
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.48 kb
#include <iostream>
#include <fstream>
#include <set>
#include <vector>
using namespace std;

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

const int maxN = 1e5 + 5;
const int maxM = 2e5 + 5;

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

bool check[maxN];
int tin[maxN], low[maxN], pas = 0, length = 0;

void comp_noua(int u, int v) {
    length += 1;
    while(true) {
        int a = muchii.back().first, b = muchii.back(). second;
        muchii.pop_back();
        componenta[length].insert(a);
        componenta[length].insert(b);
        if(u == a && v == b)
            return ;
    }
}

void dfs(int node, int p = -1) {
    check[node] = true;
    tin[node] = low[node] = ++pas;

    for(int to : g[node]) {
        if(to == p) continue;
        if(check[to]) {
            low[node] = min(low[node], tin[to]);
        } else {
            muchii.push_back({node, to});
            dfs(to, node);

            low[node] = min(low[node], low[to]);
            if(low[to] >= tin[node])
                comp_noua(node, to);
        }
    }
}

int 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 << length << "\n";
    for(int i = 1; i <= length; ++i, fout << '\n')
        for(auto v : componenta[i])
            fout << v << " ";

    return 0;
}