[BOI 2003]团伙

洛谷 P1892

注意题目里只叙述了两条规则:

• 我的朋友的朋友是我的朋友
• 我的敌人的敌人是我的朋友

而敌人的朋友、朋友的敌人如何并没有交待

记录结点 u 的朋友有哪些，敌人有哪些就好了

#include 
#include 
#include 
#include 
#include 
using namespace std;
const int MAXN=1000+1,MAXM=5000+1;
int f[MAXN],u[MAXM],v[MAXM],r[MAXN],h[MAXN];
vectoremy[MAXN],fri[MAXN];
inline int find(int x) {
	return f[x]==x?x:find(f[x]);
}
inline void merge(int u,int v) {//启发式合并
	int f1=find(u),f2=find(v);
	if(f1==f2) return;
	if(h[f1]>h[f2]) {
		f[f2]=f1;
	} else if(h[f1]enemy,1->firend
		r[i]=read();
		scanf("%d %d",&u[i],&v[i]);
		if(r[i]==1) {
			fri[u[i]].push_back(v[i]);
			fri[v[i]].push_back(u[i]);
		} else {
			emy[u[i]].push_back(v[i]);
			emy[v[i]].push_back(u[i]);
		}
	}
	for(int i=1;i<=m;i++) {
		int a=u[i],b=v[i];
		if(r[i]==1) {
			merge(a,b);//a和b是朋友
			for(int j=0;j