代码

#include <bits/stdc++.h>
using namespace std;
const int N = 1005,M = 100005;
//\
   i 的老大       关系            老大个数
int fa[N];bool a[N][N];vector<int> f;
int find(int x){	// 找老大
	if (fa[x] == x)	return x;
	return fa[x] = find(fa[x]);
}
void merge(int x,int y){	// 合并团伙
	fa[find(y)] = find(x);
}
int main(int argc, char **argv){
	for (int i = 1;i < N;i++)	fa[i] = i;
	int n,m;
	cin >> n >> m;
	for (int i = 0;i < m;i++){
		bool op;int x,y;
		cin >> op >> x >> y;
		if(!op){	// 是朋友，直接合并
			merge(x,y);
		}else{	// 不是朋友，找敌人
			a[x][y] = 1;
			a[y][x] = 1;
			for (int i = 1;i <= n;i++){	// 找敌人的敌人
				if (a[x][i])	merge(y,i);
				if (a[y][i])	merge(x,i);
			}
		}
	}
	for (int i = 1;i <= n;i++)	find(i);	// 统一一下老大
	for (int i = 1;i <= n;i++){	// 找有多少个老大
		if (!count(f.begin(),f.end(),fa[i])){
			f.push_back(fa[i]);
		}
	}
	cout << f.size();
	return 0;
}

给代码加注释 代码转载于@

代码

#include<iostream>
#include<cstdio>
#include<vector>
#include<queue>
#include<cstring>
using namespace std;
const int N=1005;

vector<int> fri[N];//朋友的
vector<int> ene[N];//敌人的
bool vis[N];
queue<int> q;

int solve(int n){
	memset(vis,0,sizeof(vis));
	int ans=0;
	for(int i=1;i<=n;i++){
		if(vis[i])continue;
		ans++;
		vis[i]=1;
		q.push(i);
		while(!q.empty()){
			int u=q.front();
			q.pop();
			for(int j=0;j<fri[u].size();j++){
				if(!vis[fri[u][j]]){
					vis[fri[u][j]]=1;
					q.push(fri[u][j]);
				}
			}
			for(int j=0;j<ene[u].size();j++){
				int t=ene[u][j];
				for(int k=0;k<ene[t].size();k++){
					if(!vis[ene[t][k]]){
						vis[ene[t][k]]=1;
						q.push(ene[t][k]);
					}					
				}

			}
		}
	}
	return ans;
}
int main(){
    int n,m;
	cin>>n>>m;
	while(m--){
		int p,a,b;
		scanf("%d%d%d",&p,&a,&b);
		if(p){
			ene[a].push_back(b);
			ene[b].push_back(a);
		}else{
			fri[a].push_back(b);
			fri[b].push_back(a);
		}
	}
	printf("%d",solve(n));
    return 0;
}

#include<iostream>
#include<cstdio>
#include<vector>
#include<queue>
#include<cstring>
using namespace std;
const int N=1005;

vector<int> fri[N];
vector<int> ene[N];
bool vis[N];
queue<int> q;

int solve(int n){
	memset(vis,0,sizeof(vis));
	int ans=0;
	for(int i=1;i<=n;i++){
		if(vis[i])continue;
		ans++;
		vis[i]=1;
		q.push(i);
		while(!q.empty()){
			int u=q.front();
			q.pop();
			for(int j=0;j<fri[u].size();j++){
				if(!vis[fri[u][j]]){
					vis[fri[u][j]]=1;
					q.push(fri[u][j]);
				}
			}
			for(int j=0;j<ene[u].size();j++){
				int t=ene[u][j];
				for(int k=0;k<ene[t].size();k++){
					if(!vis[ene[t][k]]){
						vis[ene[t][k]]=1;
						q.push(ene[t][k]);
					}					
				}

			}
		}
	}
	return ans;
}
int main(){
    int n,m;
	cin>>n>>m;
	while(m--){
		int p,a,b;
		scanf("%d%d%d",&p,&a,&b);
		if(p){
			ene[a].push_back(b);
			ene[b].push_back(a);
		}else{
			fri[a].push_back(b);
			fri[b].push_back(a);
		}
	}
	printf("%d",solve(n));
    return 0;
}