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

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
#define int long long
int n,m,idx;
map<string,int> getid;
map<int,string> id_to_name;
map<int,int> degree;
vector<int> adj[N];

void solve(){
	
	vector<string> res_name;

	int i_degree,sum_degree=0;
	for(int i=1;i<=idx;i++){
		i_degree=degree[i];
		sum_degree=0;
		for(int j:adj[i]){
			sum_degree+=degree[j]; 
		}
		if(sum_degree<i_degree*i_degree){
			res_name.push_back(id_to_name[i]);
		}
	}
	
	sort(res_name.begin(),res_name.end());
	
	if(!res_name.empty()){
		for(string name:res_name){
			cout<<name<<" ";
		}
	}else{
		cout<<"None";
	}
	return;
}

signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	
	cin>>n>>m;
	string su,sv;
	for(int i=1;i<=m;i++){
		cin>>su>>sv;
		if(getid.find(su)==getid.end()){
			idx++;
			getid[su]=idx;
		}
		int num_su=getid[su];
		if(getid.find(sv)==getid.end()){
			idx++;
			getid[sv]=idx;
			
		}
		int num_sv=getid[sv];
		adj[num_su].push_back(num_sv);
		adj[num_sv].push_back(num_su);
		id_to_name[num_su]=su;
		id_to_name[num_sv]=sv;
		degree[num_su]++;
		degree[num_sv]++;
	}
	
	solve();
    return 0;
}