Cod sursa(job #3137043)

Utilizator racsosabeVictor Racso Galvan Oyola racsosabe Data 10 iunie 2023 19:13:47
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.25 kb
#include<bits/stdc++.h>
using namespace::std;
 
const int N = 100000 + 5;

int n;
int m;
int T;
int len;
int cnt;
int low[N];
int tin[N];
int order[N];
vector<int> G[N];
vector<int> ans[N];
 
void DFS(int u) {
    order[++len] = u;
    tin[u] = low[u] = ++T;
    for(int v : G[u]) {
        if(tin[v]) {
            low[u] = min(low[u], tin[v]);
        }
        else{ 
            int x = len;
            DFS(v);
            low[u] = min(low[u], low[v]);
            if(low[v] >= tin[u]) {
                ans[++cnt].emplace_back(u);
                while(len > x) {
                    ans[cnt].emplace_back(order[len--]);
                }
            }
        }
    }
}

void setIO(string name) {
    string inputname = name + ".in";
    string outputname = name + ".out";
    freopen(inputname.c_str(), "r", stdin);
    freopen(outputname.c_str(), "w", stdout);
}

int main(){
    setIO("biconex");
	scanf("%d %d", &n, &m);
    for(int i = 0; i < m; i++) {
        int u, v;
        scanf("%d %d", &u, &v);
        G[u].emplace_back(v);
        G[v].emplace_back(u);
    }
    DFS(1);
    printf("%d\n", cnt);
    for(int i = 1; i <= cnt; i++) {
        for(int j = 0; j < ans[i].size(); j++) printf("%d%c", ans[i][j], " \n"[j + 1 == ans[i].size()]);
    }
	return 0;
}