查看原帖
1118614
I_Love_DS楼主2025/1/15 14:57
#include<iostream>
#include<string>
using namespace std;
int n,m,f[1001],enm[1001];  //f存放节点的父亲,enm存放每个人的敌人 
int find(int x)            //寻找x的祖先 
{
    while(f[x]!=x) x=f[x]; //不断更新寻找祖先
    return x;
}
void hebing(int x,int y)    //中文看得懂吧 
{
    x=find(x);y=find(y);  //无判定超简单合并_(:з」∠)_照顾一下和我一样的萌新
    if(x==y) return;
    f[y]=x;
    return;
}
int main()
{
     cin>>n>>m;
     for(int i=1;i<=n;i++)
        f[i]=i;
    for(int i=1;i<=m;i++)
    {
        int p,q;
        char c;
        cin>>c>>p>>q;
        if(c=='F') hebing(p,q);  //是朋友就合并 
        else {
                if(enm[p]==0) enm[p]=find(q);
              else hebing(q,enm[p]);  //一个人有两个或更多敌人,合并他们 
              if(enm[q]==0) enm[q]=find(p);
              else hebing(p,enm[q]);
            } 
    }
    int count[1001]={0};
    for(int i=1;i<=n;i++)
        count[find(i)]++;
    int cnt=0;
    for(int i=1;i<=n;i++)
        if(count[i]) cnt++; //统计,做得不是很简洁 
    cout<<cnt;
 }

第一篇题解。

题面中说了最多的团体数,难道不是

    int cnt=0;
    for(int i=1;i<=n;i++)
        cnt += count[i] / 2; //统计,做得不是很简洁 
    cout<<cnt;
 }

吗?

2025/1/15 14:57
加载中...