Cod sursa(job #2917203)

Utilizator florinrafiliuRafiliu Florin florinrafiliu Data 3 august 2022 19:05:18
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.49 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <set>
using namespace std;

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

const int maxN = 1e5 + 5;

int timp = 0, length = 0;
int low[maxN], tin[maxN];

bool visit[maxN];

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

void comp_noua (int node, int to) {
    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(node == a && to == b)
            return ;
    }
}

void dfs(int node, int dad = -1) {
    visit[node] = true;

    tin[node] = low[node] = ++timp;

    for(int to : g[node]) {
        if(to == dad) continue;

        if(visit[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 j : componenta[i])
            fout << j << " ";

    return 0;
}