Graph Cutting

#include <bits/stdc++.h>
#define F first
#define S second
#define MP make_pair
using namespace std;
int n, m;

struct Bridges{
  vector<int> c, h;
  void dfs(vector<pair<int, int> >* g, int x, int pe, int d, vector<int>& ns){
    if (h[x]) return;
    h[x]=d; ns.push_back(x);
    for (auto nx : g[x]){
      if (nx.S!=pe){
        dfs(g, nx.F, nx.S, d+1, ns);
        h[x]=min(h[x], h[nx.F]);
      }
    }
    if (h[x]==d){
      while (ns.size()>0){
        int t=ns.back();c[t]=x;
        ns.pop_back();
        if (t==x) break;
      }
    }
  }
  Bridges(vector<pair<int, int> >*g, int n) : c(n+1), h(n+1){
    vector<int> ns;
    for (int i=1; i<=n; ++i) dfs(g, i, -1, 1, ns);
  }
};

struct Biconnected{
  vector<int> cut, h, d, used;
  vector<map<int, vector<int> > > bg;
  vector<pair<int, int> > es;
  int cc;
  void dfs(vector<int>* g, int x, int p) {
    h[x]=d[x];
    int f=0;
    for (int nx:g[x]){
      if (nx!=p){
        if (!used[nx]) es.push_back({x, nx});
        if (d[nx]==0){
          ++f; d[nx]=d[x]+1;
          int ts=es.size();
          dfs(g, nx, x);
          h[x]=min(h[x], h[nx]);
          if (h[nx]>=d[x]){
            cut[x]=1;
            while ((int)es.size()>=ts){
              auto e=es.back();
              bg[e.F][cc].push_back(e.S);
              bg[e.S][cc].push_back(e.F);
              used[e.S]=1;used[e.F]=1;
              es.pop_back();
            }
            used[x]=0; ++cc;
          }
        }
        h[x]=min(h[x], d[nx]);
      }
    }
    if (p==0){
      if (f>1) cut[x]=1;
      else cut[x]=0;
    }
  }
  Biconnected(vector<int>*g, int n):cut(n+1), h(n+1), d(n+1), used(n+1), bg(n+1){
    cc=1;
    for (int i=1; i<=n; ++i){
      if (d[i]==0){
        d[i]=1;
        dfs(g, i, 0);
      }
    }
  }
};


vector<pair<int, int> >  rt1[101010];
vector<int>              rt2[101010];
vector<pair<int, int> > es;
int main(){
  ios_base::sync_with_stdio(0); cin.tie(0);
  cin >> n >> m;
  for (int i=1; i<=m; ++i){
    int a, b;
    cin >> a >> b;
    es.push_back(MP(a, b));
    rt1[a].push_back(MP(b, i));
    rt1[b].push_back(MP(a, i));
    rt2[a].push_back(b);
    rt2[b].push_back(a);
  }
  int ap=0;
  int br=0;
  Bridges g(rt1, n);
  for (int i=1; i<=m; ++i){
    if (g.c[es[i-1].F]!=g.c[es[i-1].S]){
//       cout << "Bridge " << es[i-1].F << ", " << es[i-1].S << endl;
      ++br;
    }
  }
  Biconnected r(rt2, n);
  for (int i=1; i<=n; ++i){
    if (r.cut[i]){
      ++ap;
//       cout << "cut " << i << endl;
    }
  }
  cout << ap << " " << br << endl;
}

Test 1

Verdict: ACCEPTED