AtCoder が提供しているABC（AtCoder Beginner Contest）350 のD問題をC++とPythonで解いてみました。ABC350は、2024年4月20日21:00に実施されました。
AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。
D問題 New Friends（Difficulty : 773）
問題はリンク先をご覧ください。
グラフとして連結している頂点と辺の個数を求めます。AtCoder Problems による Difficulty は 773 でした。
解答案
$N$ 人のユーザを頂点、友達関係を辺とするグラフを考えます。連結しているグラフに含まれている頂点と辺の数が分かれば、それぞれの連結成分毎に
頂点の個数から2つ選ぶ組み合わせの数 － 辺の個数
の総和が求める解となります。左の項は、$_nC_2 = n \times (n \;-\;1 ) / 2$ となります。
C++ プログラム例（ABC350D）
グラフの辺を設定して（28ー33行目）、DFSで連結成分に含まれる頂点と辺の個数を求めてます。DFSのコードは定番コードとなっています。
辺は始点と終点で2回カウントしているため2で割っています（43行目）。
以下が、C＋＋プログラムとなります。
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
vector<vector<int>> G;
vector<bool> seen;
set<int> this_group;
ll this_group_e;
void dfs(int v)
{
seen[v] = true;
this_group.insert(v);
this_group_e += G[v].size();
for (auto next_v : G[v]) {
if (!seen[next_v]) {
dfs(next_v);
}
}
}
int main()
{
int n, m;
cin >> n >> m;
G.resize(n + 1);
for (int i = 0; i < m; ++i) {
int a, b;
cin >> a >> b;
G[a].push_back(b);
G[b].push_back(a);
}
ll result = 0;
seen.assign(n + 1, false);
for (int i = 1; i <= n; ++i) {
if (!seen[i]) {
this_group.clear();
this_group_e = 0;
dfs(i);
ll s = this_group.size();
result += s * (s - 1) / 2 - this_group_e / 2;
}
}
cout << result << endl;
return 0;
}AC（Accepted＝正しいプログラム）と判定されました。
Python プログラム例（ABC350D）
Python 版も基本的な考え方は同じです。再帰関数の呼び出し回数を増やしています（2、5行目）。以下となります。
"""AtCoder Beginner Contest 350 D"""
import sys
LIMIT = 10**6
sys.setrecursionlimit(LIMIT)
def dfs(v):
global G, seen, this_group, this_group_e
seen[v] = True
this_group.add(v)
this_group_e += len(G[v])
for next_v in G[v]:
if not seen[next_v]:
dfs(next_v)
n, m = map(int, input().split())
G = [[] for i in range(n + 1)]
seen = [False] * (n + 1)
for i in range(m):
a, b = map(int, input().split())
G[a].append(b)
G[b].append(a)
result = 0
for i in range(1, n + 1):
if not seen[i]:
this_group = set()
this_group_e = 0
dfs(i)
s = len(this_group)
result += s * (s - 1) // 2 - this_group_e // 2
print(result)こちらも「AC」と判定されました。
最後に
ABC269からブログで記事していますが、当初はグラフの問題はほとんど解けませんでした。いまは典型的な問題であれば解けるようになりました。
引き続き ABC の問題を紹介していきます。
