C++ 代码

#include <iostream>
#include <vector>
#include <unordered_map>
#include <map>
using namespace std;
const int N = 2000;

unordered_map<string, int> s2n;
unordered_map<int, string> n2s;
map<string, int> ans;
vector<int> g[N];
bool vis[N];
int Time[N];
int cnt, total, maxTime, head;

int dfs(int x) //深搜求连通域
{
    if (Time[x] > maxTime)
    {
        maxTime = Time[x];
        head = x;
    }
    total += Time[x];
    int res = 1;
    vis[x] = true;
    for (int i = 0; i < g[x].size(); i++)
        if (!vis[g[x][i]])
            res += dfs(g[x][i]);
    return res;
}

int main()
{
    int n, k, cnt = 0;
    cin >> n >> k;
    for (int i = 0; i < n; i++)
    {
        string a, b;
        int t;
        cin >> a >> b >> t;
        if (s2n.find(a) == s2n.end())
            s2n[a] = cnt++, n2s[cnt - 1] = a;
        if (s2n.find(b) == s2n.end())
            s2n[b] = cnt++, n2s[cnt - 1] = b;
        Time[s2n[a]] += t, Time[s2n[b]] += t;
        g[s2n[a]].push_back(s2n[b]);
        g[s2n[b]].push_back(s2n[a]);
    }
    int members, gang = 0;
    for (int i = 0; i < cnt; i++)
    {
        if (!vis[i])
        {
            total = 0, maxTime = -1;
            members = dfs(i);
            if (members > 2 && total >> 1 > k) // 成员必须大于2，且连通域总边权（通话总时间除以2）要大于k
            {
                gang++;
                ans[n2s[head]] = members;
            }
        }
    }
    cout << gang << endl;
    for (auto res : ans)
        cout << res.first << " " << res.second << endl;
    return 0;
}