ในข้อนี้ โดยไม่เสียนัย เราสามารถมองว่าผู้ใช้แต่ละคนเป็นโหนดและความเป็นเพื่อนระหว่างสองผู้ใช้เป็นเส้นเชื่อม จึงสรุปได้ว่าโจทย์ต้องการนับจำนวนคู่โหนดที่ตรงตามเงื่อนไขของโจทย์ เราจึงจะแบ่งการนับจำนวนคำตอบออกเป็น 2 กรณีตามที่โจทย์กำหนดไว้ดังนี้

กรณีแรก - คู่โหนดไม่ได้ไม่มีเส้นเชื่อมหากัน แต่มีเซตของโหนดที่ติดกันเหมือนกัน

การเทียบเซตของจำนวนเต็ม ว่าเหมือนกันหรือไม่ สามารถทำได้ด้วยการใช้ Rolling Hash Algorithm นิยามให้ $H(S) := \sum \limits_{i=1}^{|S|}B^{S_i}$ เป็น Hash Function เมื่อ $S$ เป็นเซตของจำนวนเต็มที่ต้องการจะ Hash และ $S_i$ เป็นสมาชิกของ $S$ ตัวที่ $i$ ที่มาของฟังก์ชั่นนี้คือการที่เราสามารถแสดงเซตของจำนวนเต็มให้อยู่ในรูปของ bitstring (สายอักขระที่ประกอบไปด้วยเลข 0 และ 1) ได้ด้วยการให้อักขระที่ $i$ เป็น 1 เมื่อมี $i$ เป็นสมาชิกของเซตหรือ 0 ในทางตรงกันข้าม เช่น $\{1, 3, 4\}$ สามารถแสดงในรูปของ bitstring คือ 1101 สำหรับฟังก์ชั้นนี้ เป็นการคำนวณค่าของ bitstring ในเลขฐาน $B$ กล่าวคือหาก $i$ เป็นสมาชิกของเซต $S$ เราจะบวกค่าของ $B^i$ เข้าไป

ค่าของ $H(S)$ จะอยู่ในรูปของจำนวนเต็มที่สามารถนำไปเทียบกับค่า Hash อื่นๆ ได้ โดยอาจเก็บค่าในตัวแปรประเภท long long แล้วปล่อยให้ overflow หรืออาจนำค่าไป $\mod p$ โดย $p$ นิยมใช้เป็นจำนวนเฉพาะ

อย่างไรก็ตาม วิธี Rolling Hash มีข้อเสียคือมีโอกาสที่เซตสองเซตที่ต่างกัน กลับมีค่า Hash ที่ตรงการ ดังนั้นควรเลือกจำนวนนับ $B$ เป็นจำนวนเฉพาะขนาดใหญ่ เพื่อลดโอกาสการเกิดข้อผิดพลาดนี้ขึ้น

เราจะทำการเก็บ Hash ต่างๆ ของเซตของโหนดติดกันของแต่ละโหนด เพื่อมานับโหนดที่มีค่า Hash ซ้ำกัน ซึ่งอาจจะใช้ stl_map หรือทำวิธี Two Pointer ก็ได้

กำหนดให้ $H$ เป็นเซตของค่า Hash ของแต่ละโหนด โดยเราจะไม่สนใจตัวที่ซ้ำกัน จะได้ว่าจำนวนคู่โหนดที่ตรงตามเงื่อนไขแรกจะเป็น $\sum \limits_{i=1}^{|H|} \frac{cnt_i \cdot (cnt_i - 1)}{2}$ เมื่อ $cnt_i$ คือจำนวนโหนดที่มีค่า Hash ตรงกับสมาชิกของ $H$ ตัวที่ $i$

กรณีที่สอง - คู่โหนดมีเส้นเชื่อมหากัน แต่มีเซตของโหนดที่ติดกันโดยไม่รวมโหนดที่อยู่ตรงปลายของเส้นเชื่อมนี้ เหมือนกัน

เนื่องจากเป็นการเทียบเซตของจำนวนเต็มเช่นเดิม จึงสามารถใช้วิธี Rolling Hash ดังที่ได้กล่าวไว้ในกรณีแรกได้ แต่เนื่องจากในกรณีนี้ คู่โหนดจะต้องมีเส้นเชื่อมหากัน จึงมีคู่โหนดที่ตรงตามกรณีนี้ได้เพียง $M$ (จำนวนเส้นเชื่อม) คู่เท่านั้น ดังนั้น เราจะทำการไล่ทีละเส้นเชื่อมแล้วพิจารณาคู่โหนดตรงปลายของเส้นเชื่อมทีละเส้น

กำหนดให้คู่โหนดที่ปลายเส้นเชื่อมที่กำลังพิจารณาอยู่เป็น $u$ และ $v$ และเซตของโหนดที่ติดกันของโหนดสองโหนดนี้เป็น $S_u$ และ $S_v$ ตามลำดับ เนื่องจากการเทียบค่า Hash จะต้องไม่รวมโหนดที่อยู่ตรงปลายอีกฝั่งของเส้นเชื่อม จึงต้องลบค่า Hash ของโหนดปลายตรงข้ามของเส้นเชื่อมออก ดังนั้นค่า Hash ของโหนด $u$ และ $v$ ที่เราจะนำมาเทียบจึงมีค่าเป็น $H(S_u) - B^{v}$ และ $H(S_v) - B^{u}$ หากสองค่านี้มีค่าเท่ากัน จะได้ว่า $u$ และ $v$ เป็นคู่โหนดที่ตรงตามกรณีนี้

โค้ดตัวอย่างดังนี้

#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 5;
const int B = 1e9 + 7;

int n, m;
long long ans, ppow[N], hsh[N];
vector<pair<int, int> > E;
map<long long, int> mp;

int main() {
  ppow[0] = 1;
  for (int i = 1; i < N; i++)
    ppow[i] = ppow[i - 1] * B;

  scanf("%d %d", &n, &m);
  for (int i = 1, u, v; i <= m; i++) {
    scanf("%d %d", &u, &v);
    hsh[u] += ppow[v], hsh[v] += ppow[u];
    E.emplace_back(u, v);
  }

  for (int i = 1; i <= n; i++)
    ++mp[hsh[i]];
  for (auto p : mp)
    ans += 1ll * (p.second) * (p.second - 1) / 2;
  for (pair<int, int> e : E)
    if (hsh[e.first] - ppow[e.second] == hsh[e.second] - ppow[e.first])
      ++ans;
  printf("%lld", ans);

  return 0;
}

Time Complexity: $\mathcal{O}((N + M) \log N)$