60分求解
查看原帖
60分求解
759932
Lyq13579楼主2024/3/4 22:10
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e3+10;
typedef pair<int,int>P;
int father[maxn],rankk[maxn],ans,diren[maxn][maxn],dire[maxn];
//father[i]:i的父亲  rankk[i]:i这棵树的高度
void init(int n)//初始化函数
{
    for(int i=1;i<=2*n;i++)
    {
        father[i]=i;
        rankk[i]=1;
    }
}
int find(int x)//找根函数,进行路径压缩
{
    if(father[x]==x) return x;
    else return father[x]=find(father[x]);
    cout<<1;
}
void unite(int x,int y)//合并操作
{
    x=find(x); y=find(y);
    if(x==y) return;
    father[y]=x;
}
int n,m,p,q;
char c;
int main(){
	for(int i=1;i<=1010;i++){
		dire[i]=1;
	}
    cin>>n>>m;
    init(n);
    while(m--)
    {
        cin>>c>>p>>q;
        if(c=='F'){
        	unite(p,q);
		}
		if(c=='E'){
			diren[p][dire[p]]=q;
			dire[p]++;
			diren[q][dire[q]]=p;
			dire[q]++;
			for(int i=1;i<dire[p];i++){
				unite(q,diren[p][i]);
			}
			for(int i=1;i<dire[q];i++){
				unite(p,diren[q][i]);
			}
		}
    }
    for(int i=1;i<=n;i++){
        if(father[i]==i){
        	ans++;
        }
    }
    cout<<ans;
    return 0;
}
2024/3/4 22:10
加载中...