lowlinkの実装

lowlinkというのは、例えば連結なグラフがあった場合、どこの頂点やどこの辺をなくすと連結じゃなくなるかを確認する方法です。
なくなると連結じゃなくなる頂点を関節、辺を橋といいます。

備忘録。

まず実装

int lowlink(int n,int m, vector<vector<int>>rotti)
{
  //与えられるグラフは連結なグラフが条件
  vector<int>stack{1};
  vector<int>num(n,-1),low(n,-1);
  int count=1,hako,hako2,leng=1,check;
  num[0]=0;
  low[0]=0;
  hako2=1000000000;
  while (leng>0){
    hako=stack[leng-1];
    check=0;
    for (int i=0;i<rotti[hako-1].size();i++){
      if (num[rotti[hako-1][i]-1]!=-1){
	if (stack[max(leng-2,0)]!=rotti[hako-1][i])hako2=min(hako2,low[rotti[hako-1][i]-1]);
	continue;
      }
      stack.emplace_back(rotti[hako-1][i]);
      num[rotti[hako-1][i]-1]=count;
      low[rotti[hako-1][i]-1]=count;
      count++;
      leng++;
      hako2=1000000000;
      check=1;
      break;
    }
    if (check==1)continue;
    low[hako-1]=min(low[hako-1],hako2);
    low[stack[max(0,leng-2)]-1]=min(low[stack[max(0,leng-2)]-1],low[hako-1]);
    stack.pop_back();
    leng--;
  }
  /*
  グループ分けの結果を出力
  for (int i=0;i<low.size();i++)cout << low[i] << " ";
  cout << endl;
  */
  //関節の個数の出力
  set<int>irane;
  int ans=0;
  for (int i=0;i<n;i++){
    irane.clear();
    for (int ipp=0;ipp<rotti[i].size();ipp++)irane.insert(low[rotti[i][ipp]-1]);
    if (irane.size()>1)ans++;
  }
  cout << ans << endl;
  return 0;
}

引数に、頂点の個数N、辺の数M、連結関係を格納した二次元グラフを入れます。

どういうことをしているのかというと、グラフのそれぞれの頂点をループしているところでグループわけみたいにして、それぞれの頂点にグループの番号を降り、２つ以上のグループを連結している頂点や辺は関節や橋だとするということです。

図で解説します。

まず、以下のようなグラフがあるとします。

最初に、DFSなどでスタートした地点から順番に番号をつけていきましょう。今回は左上からスタートすることにします。
以下のようになったとします。

このグラフでループしてるのは以下の２つです

よって２つのグループに分けます。例えば１と２にしてみます。

それぞれの頂点にグループの番号を書いてみます。

２つ以上のグループを結んでいる辺やその辺とつながっている頂点が橋や関節になります（←理由説明するのめんどくさい><）。

こういうことです（？）。
これを実装したのがさっきのコードになります。今は関節の個数を出力するようになっていますが、下に出力するコードをつけたすだけで橋の個数も、関節になっている頂点の番号も出力することができます。（頂点の番号を格納しているのがnum,グループの番号を格納しているのがlow）。

例えば下のコードなどで受け取ったグラフの関節の個数を出力できます。

#include <bits/stdc++.h>
using namespace std;
int lowlink(int n,int m, vector<vector<int>>rotti)
{
  //与えられるグラフは連結なグラフが条件
  vector<int>stack{1};
  vector<int>num(n,-1),low(n,-1);
  int count=1,hako,hako2,leng=1,check;
  num[0]=0;
  low[0]=0;
  hako2=1000000000;
  while (leng>0){
    hako=stack[leng-1];
    check=0;
    for (int i=0;i<rotti[hako-1].size();i++){
      if (num[rotti[hako-1][i]-1]!=-1){
	if (stack[max(leng-2,0)]!=rotti[hako-1][i])hako2=min(hako2,low[rotti[hako-1][i]-1]);
	continue;
      }
      stack.emplace_back(rotti[hako-1][i]);
      num[rotti[hako-1][i]-1]=count;
      low[rotti[hako-1][i]-1]=count;
      count++;
      leng++;
      hako2=1000000000;
      check=1;
      break;
    }
    if (check==1)continue;
    low[hako-1]=min(low[hako-1],hako2);
    low[stack[max(0,leng-2)]-1]=min(low[stack[max(0,leng-2)]-1],low[hako-1]);
    stack.pop_back();
    leng--;
  }
  /*
  グループ分けの結果を出力
  for (int i=0;i<low.size();i++)cout << low[i] << " ";
  cout << endl;
  */
  //関節の個数の出力
  set<int>irane;
  int ans=0;
  for (int i=0;i<n;i++){
    irane.clear();
    for (int ipp=0;ipp<rotti[i].size();ipp++)irane.insert(low[rotti[i][ipp]-1]);
    if (irane.size()>1)ans++;
  }
  cout << ans << endl;
  return 0;
}



int main()
{
  int n,m,a,b;
  cin >> n >> m;
  vector<vector<int>>rotti(n);
  for (int i=0;i<m;i++){
    cin >> a >> b;
    rotti[a-1].emplace_back(b);
    rotti[b-1].emplace_back(a);
  }
  lowlink(n,m,rotti);
}

たぶん見る人いないと思うので適当に書きました。あとで丁寧に書く。
あと戻り値をゼロにして関数の中で出力しているのは軽く確認のためです。書き直さなきゃ…