Cod sursa(job #2233377)

Utilizator DjokValeriu Motroi Djok Data 23 august 2018 07:07:20
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.13 kb
//#pragma GCC optimize("Ofast")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include <bits/stdc++.h>
using namespace std;

const int N = 100005;

int i, n, m, x, y, timer, tin[N], fup[N];
vector<int> lda[N], v;
vector<vector<int>> ans;

void dfs(int x) {
  tin[x] = fup[x] = ++timer;
  v.push_back(x);

  for(auto to : lda[x])
    if(tin[to]) fup[x] = min(fup[x], tin[to]);
    else {
      dfs(to);
      fup[x] = min(fup[x], fup[to]);
      if(fup[to] >= tin[x]) {
        ans.push_back(vector<int>());
        while(1) {
          ans.back().push_back(v.back());
          v.pop_back();
          if(ans.back().back() == to) break;
        }
        ans.back().push_back(x);
      }
    }
}

int main() {
  freopen("biconex.in", "r", stdin);
  freopen("biconex.out", "w", stdout);

  scanf("%d %d", &n, &m);
  for(i = 1; i <= m; ++i) {
    scanf("%d %d", &x, &y);
    lda[x].push_back(y);
    lda[y].push_back(x);
  }

  dfs(1);

  printf("%d\n", (int)ans.size());
  for(auto curr : ans) {
    for(auto it : curr) printf("%d ", it);
    puts("");
  }

  return 0;
}