1 条题解

  • 0
    @ 2025-10-10 19:30:57

    C++ :

    #include<bits/stdc++.h>
    using namespace std;
    #define N 1010
    //f:存储每个节点的父节点 
    int n,m,ans,f[N],e[N];
    char c;
    
    //压缩路径求解x的根
    int find(int x){
    	//x的父直接指向x的根 
    	return x == f[x]?x:f[x]=find(f[x]);
    } 
    
    //将x和y合并到同一个集合 
    void merge(int x,int y){
    	int fx = find(x);
    	int fy = find(y);
    	//如果x和y不在一个集合 
    	if(fx != fy){
    		f[fx] = fy;
    	} 
    }
    
    int main(){
    	cin>>n>>m;
    	for(int i = 1;i <= 2 * n;i++) f[i] = i;
    	int x,y;
    	//m个关系
    	for(int i = 1;i <= m;i++){
    		cin>>c>>x>>y;
    		//朋友关系直接合并 
    		if(c == 'F') merge(x,y);
    		else if(c == 'E'){
    			//敌人,假设x+n是x的敌人 
    			merge(x+n,y);
    			merge(y+n,x);
    		}
    	} 
    	
    	for(int i = 1;i <= n;i++){
    		if(f[i] == i) ans++;
    	} 
    	
    	cout<<ans;
    	return 0;
    } 
    
    
    • 1

    信息

    ID
    843
    时间
    1000ms
    内存
    512MiB
    难度
    (无)
    标签
    递交数
    0
    已通过
    0
    上传者