SOS
  • 板块学术版
  • 楼主HeiGi
  • 当前回复4
  • 已保存回复4
  • 发布时间2023/1/6 16:14
  • 上次更新2023/10/24 05:23:13
查看原帖
SOS
574852
HeiGi楼主2023/1/6 16:14

萌新刚学OI,脑子不太好用,刚刚自学并查集,MLE求助,看起来没问题

/****written by 574852****/
#include<bits/stdc++.h>
using namespace std;
int n,m;
int fa[1001];
void join(int,int);
int find(int);
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    while(cin>>n && n)
    {
        int ans=-1,x,y;
        cin>>m;
        for(int i=1;i<=n;i++)
        {
            fa[i]=i;
        }
        for(int i=1;i<=m;i++)
        {
            cin>>x>>y;
            join(x,y);
        }
        for(int i=1;i<=n;i++)
        {
            if(i == find(i))
            {
                ans++;
            }
        }
        cout<<ans<<'\n';
    }
    return 0;
}
int find(int x)
{
    if(fa[x]!=x)
    {
        return fa[x]=find(x);
    }
    return fa[x];
}
void join(int x,int y)
{
    fa[find(x)]=find(y);
}

具体情况

2023/1/6 16:14
加载中...