算法题：朋友

问题描述

同学们应该学会多交一些好朋友。朋友关系是相互的，A 是 B 的好朋友，则 B 也是 A 的好朋友。朋友关系是不传递的，A 是 B 的好朋友，B 是 C 的好朋友，但 A 和 C 不一定是好朋友。现在给出某小学部分同学之间的朋友关系，请编程统计朋友最多的人有多少个好朋友。

输入格式

输入共m+1行。
第1行是两个整数n和m，分别表示同学总人数和朋友关系对数。
第2行到第m+1行，描述了m对朋友关系。每行两个用单个空格隔开的同学姓名。
每个人的姓名仅由小写字母组成，且1≤姓名的长度≤10。

输出格式

输出共 1 行。
一个整数，表示朋友最多的人有多少个好朋友。

样例1

输入

4 3
lucy lily
jam lily
jam peter

输出

2

对于样例1的解释

4个人，3对朋友关系。lucy只有一个朋友lily；jam有两个朋友lily和peter；lily有两个朋友lucy和jam；
peter只有一个朋友jam。
所以lily和jam朋友最多，都是2个。

数据范围

50%以上的测试点输入数据保证朋友关系没有重复。
100%的测试点输入数据保证2≤n≤100，1≤m≤1000，且没有自己跟自己的朋友关系。

解决方案

思路

深度优先搜索

代码

#include <iostream>
#include <vector>
#include <map>

using namespace std;

map<string, vector<string>> g;

int dfs(string name, string fa) {
    int ans = g[name].size() - 1;
    for (auto item: g[name]) {
        if (item != fa) {
            ans += dfs(item, name);
        }
    }

    g.erase(name);
    return ans;
}

int main() {
    int n, m;
    cin >> n >> m;


    for (int i = 0; i < m; ++i) {
        string buf1, buf2;
        cin >> buf1 >> buf2;

        g[buf1].push_back(buf2);
        g[buf2].push_back(buf1);
    }

    int ans = 0;
    while (!g.empty()) {
        auto item = *(g.begin());
        int t = dfs(item.first, "");
        ans = max(ans, t);
    }

    cout << ans;

    return 0;
}