閉路

分割してできる最大の連結成分数

#include <bits/stdc++.h>
using namespace std;

int main() {
  int n = 5; // 頂点数
  int k = n / 2; // 分割してできる最大の連結成分数
}

頂点 1 と頂点 2、頂点 2 と頂点 3、... 頂点 n-1 と頂点 n、頂点 n と頂点 1 が結ばれている数珠のような閉路グラフで、任意の頂点とその頂点に繋がっている辺を消すことで、最大いくつの連結成分に分割できるかを知りたい場合。

まず任意の頂点を 1 つ消し、グラフの形状を数珠型から直線型に変える。

その後、端から偶数番目の頂点を消し、サイズ 1 の連結成分を作成していく。

なので、分割できる最大数は頂点数を 2 で割って切り下げた数になる。