Cod sursa(job #3241531)

Utilizator VanillaSoltan Marian Vanilla Data 31 august 2024 11:37:20
Problema Componente biconexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.42 kb
#include <bits/stdc++.h>
using namespace std;
string __fname = "biconex"; ifstream in (__fname + ".in"); ofstream out (__fname + ".out"); 
#define cin in 
#define cout out
const int maxn = 1e5 + 2;
vector <int> ad [maxn];
int low[maxn], tin[maxn], ct;
bitset<maxn> vis;
vector <vector <int> > rs;
vector <int> sf;

void dfs (int u, int p) {
    tin[u] = low[u] = ct++;
    sf.push_back(u);
    vis[u] = 1;
    for (int v: ad[u]) {
        if (v == p) continue;
        if (vis[v]) low[u] = min(low[u], tin[v]);
        else {
            dfs(v, u);
            if (low[v] >= tin[u]) {
                cout << u << " - " << v << "\n";
                vector <int> temp;
                rs.push_back(vector <int> (1, u));
                while (!sf.empty() && sf.back() != u) {
                    rs.back().push_back(sf.back());
                    sf.pop_back();
                }
            }
            low[u] = min(low[u], low[v]);
        }
    }
}
int main(){
  ios_base::sync_with_stdio(0); cin.tie(0); cout << fixed; cout << setprecision(10);
  int n,m;
  cin >> n >> m;
  for (int i = 0; i < m; i++){
    int x,y;
    cin >> x >> y;
    ad[x].push_back(y);
    ad[y].push_back(x);
  }
  for (int i = 1; i <= n; i++){
    if (!vis[i]) dfs(i, -1);
  }
  cout << rs.size() << "\n";
  for (auto& x: rs) {
    for (auto& y: x) {
        cout << y << " "; 
    }
    cout << "\n";
  }

  return 0;
}