自动搬运

查看原文

来自洛谷，原作者为

	x义x “我们要走多远？”“一百万年。”

搬运于2025-08-24 21:31:34，当前版本为作者最后更新于2017-10-21 13:25:09，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

萌新刚AC了本题，谈下心得吧~

以下代码

#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;
 } 

首先，要充分理解题目。 “敌人的敌人就是朋友”可以这么理解：如果一个人有两个或更多敌人，这些敌人就应该被合并。

代码中的enm数组就是记录了每个人的第一个敌人，再遇到敌人时就把这两个敌人合并。

没想出这点的话还是蛮难做的。

路径优化什么的，咳咳，都说是萌新了。

另外致萌新：如果错了一定优先检查循环条件_(:з」∠)_本人调了一小时才发现是某循环条件的“==”打成“=”了……以前学pascal的后遗症啊

至于代码注释不够清晰等问题欢迎提出~

讲得可能比那些高估咱萌新实力的大牛们稍微易懂点吧，人生中第一个题解，希望能过⁄(⁄ ⁄•⁄ω⁄•⁄ ⁄)⁄