题解 | 我朋友的朋友不是我的朋友

#include <iostream>
#include <vector>
#include <map>
#include <cstring>
#include <algorithm>
#include <string>

using namespace std;
//关于c++第一次修改键值对时其值会有默认值,(vector会初始化，int则会默认初始化为0)
int main() {
	int n, m;
	cin >> n >> m;
	map<string, int> degree;
	map<string, vector<string> > friendship;
	string v1, v2;
	for (int i = 0; i < m; i++) {
		cin >> v1 >> v2;
		degree[v1]++;
		degree[v2]++;
		friendship[v1].push_back(v2);
		friendship[v2].push_back(v1);
	}
	vector<string> ans;
	for (map<string, vector<string> >::iterator it = friendship.begin(); it != friendship.end(); it++) {
		int self = degree[it -> first];
		int sum = 0;
		vector<string>& friends = it -> second;
		for (vector<string>::iterator it2 = friends.begin(); it2 != friends.end(); it2++) {
			sum += degree[*it2];
		}
		if (self * self > sum) ans.push_back(it -> first);
	}
	if (!ans.size()) {
		cout << "None" << endl;
		return 0;
	}
	sort(ans.begin(), ans.end());
	for (vector<string>::iterator it2 = ans.begin(); it2 != ans.end(); it2++) {
		cout << *it2 << " "; 
	}
}