算法1 DFS

#include <iostream>
#include <vector>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <algorithm>

using namespace std;
int n, k, t;
string n1, n2;

unordered_map<string, int> times; // 每个人的总的通话时间
map<string, vector<string>> g; // g == the undirected graph
unordered_set<string> all;
unordered_set<string> seen;

void dfs(string cur, int& total_time, int& count, int& max_time, string& max_time_name) {
  if (seen.count(cur)) return;
  seen.emplace(cur);

  ++count;
  if (times[cur] > max_time) {
    max_time_name = cur;
    max_time = times[cur];
  }
  total_time += times[cur];
  for (const auto& nei : g[cur])
    dfs(nei, total_time, count, max_time, max_time_name);
}

int main(void) {
  cin >> n >> k;
  while (n--) {
    cin >> n1 >> n2 >> t;
    all.emplace(n1);
    all.emplace(n2);
    times[n1] += t;
    times[n2] += t;
    g[n1].emplace_back(n2);
    g[n2].emplace_back(n1);
  }

  vector<pair<string, int>> ans;
  for (const auto& cur : all) {
    if (seen.count(cur)) continue;
    int total_time = 0, count = 0, max_time = 0;
    string max_time_name = cur;
    dfs(cur, total_time, count, max_time, max_time_name);
    //printf("total_time = %d, count = %d, max_time = %d, max_time_name = %s\n",
    //    total_time, count, max_time, max_time_name.c_str());

    if (count >= 3 && total_time >> 1 > k)
      ans.emplace_back(max_time_name, count);
  }

  sort(begin(ans), end(ans));
  printf("%d\n", ans.size());
  for (const auto& p : ans)
    printf("%s %d\n", p.first.c_str(), p.second);

  return 0;
}

TODO 算法2：Disjoint Set