Cod sursa(job #2899896)

Utilizator FunnyStockyMihnea Andreescu FunnyStocky Data 9 mai 2022 17:13:44
Problema Componente biconexe Scor 30
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.67 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<int> verts;
vector<vector<int>> sol;

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

      if (mindep[b]>dep[a]) {
        vector<int> cur;
        while ((int)verts.size()>pos_start){
          cur.push_back(verts.back());
          verts.pop_back();
        }
        sol.push_back({a, b});
        if ((int)cur.size()>1) sol.push_back(cur);
      }

      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);
  }
  for (int i=1;i<=n;i++) dep[i]=-1;

  dep[1]=0;
  dfs(1);

  if ((int)verts.size()>1) sol.push_back(verts);

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