Cod sursa(job #2899900)

Utilizator FunnyStockyMihnea Andreescu FunnyStocky Data 9 mai 2022 17:23:55
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.87 kb
/// always:
#include <cstdio>
#include <string>

/// optional:
#include <cassert>
#include <cstring>
#include <iostream>
#include <vector>
#include <iomanip>
#include <algorithm>
#include <queue>

bool home = 1;
using namespace std;

typedef long double ld;
const string TASKNAME="biconex";

const int N=(int)1e5+7;
int n;
int m;
vector<int> g[N];
int dep[N];
int mindep[N];
vector<pair<int, int>> stk;
vector<vector<int>> all;

void dfs(int a) {
  mindep[a]=dep[a];
  for (auto &b:g[a]) {
    if (dep[b]==-1) {
      stk.push_back({a, b});
      dep[b]=1+dep[a];
      dfs(b);
      mindep[a]=min(mindep[a],mindep[b]);

      if(mindep[b]>=dep[a]) {
        vector<int> sol;

        while (1) {
          assert(!stk.empty());
          auto bk=stk.back();
          stk.pop_back();
          sol.push_back(bk.first);
          sol.push_back(bk.second);

          if (bk==make_pair(a,b)) break;
        }

        sort(sol.begin(),sol.end());
        sol.resize(unique(sol.begin(),sol.end())-sol.begin());

        all.push_back(sol);
      }
      continue;
    }
    if (dep[b]<dep[a]-1) {
      mindep[a]=min(mindep[a],dep[b]);
    }
  }
}

signed main() {
#ifdef INFOARENA
  home = 0;
#endif

  if(!home) {
    freopen((TASKNAME + ".in").c_str(), "r", stdin);
    freopen((TASKNAME + ".out").c_str(), "w", stdout);
  }else{
    freopen ("I_am_iron_man", "r", stdin);
  }

  scanf("%d%d",&n,&m);
  for (int i=1;i<=m;i++) {
    int a,b;
    scanf("%d%d",&a,&b);
    g[a].push_back(b);
    g[b].push_back(a);
  }
  for (int i=1;i<=n;i++) dep[i]=-1;

  for (int i=1;i<=n;i++) {
    if (dep[i]==-1) {
      stk.clear();
      dep[i]=0;
      dfs(i);
    }
  }


  cout<<(int)all.size()<<"\n";
  for (auto &v:all) {
    sort(v.begin(),v.end());
    for (auto &x:v){
      cout<<x<<" ";
    }
    cout<<"\n";
  }
}