文档章节

并查集,合根植物

o
 osc_y8yehimr
发布于 2019/03/20 18:06
字数 623
阅读 0
收藏 0

合根植物题目来源http://lx.lanqiao.cn/problem.page?gpid=T458

一开始看到这个题的时候我刚学搜索不就,一想不就是个搜索吗,有什么难的,然后直接就开始搜了,然后就很悲惨的。。超时,超时,超时。。。

再后来就知道了这个

并查集

最好先看一下我的另一篇博客再来看这个会看的更明白一点。https://www.cnblogs.com/zlhdbk/p/10566184.html

这个题的解题思路和那个什么江湖门派合并(另一篇并查集)差不多,每个植物看成是一个人,每株合并植物看成是一个门派,一开始一株植物是一个门派,各自是各自的掌门,连根现象就是门派合并的过程,最后看有几株植物,就是看还剩几个门派。

话不多说,直接看代码

#include <iostream>
using namespace std;
int tree[1000010];
struct dir{int x,y;}a[100001];
int m,n,k;
int findroot(int root)//找自己的掌门,并且压缩关系,使其只存在一级关系
{
    int start,t;
    start=root;
    while(root!=tree[root])
        root=tree[root];
    while(start!=root)
    {
        t=tree[start];
        tree[start]=root;
        start=t;
    }
    return root;
}
int main()
{
    int root1,root2,num;
    cin>>m>>n;
    num=m*n;
    for(int i=1;i<=m*n;i++)
        tree[i]=i;
    cin>>k;
    for(int i=1;i<=k;i++)
        cin>>a[i].x>>a[i].y;
    for(int i=1;i<=k;i++)
    {
        root1=findroot(a[i].x);
        root2=findroot(a[i].y);
        if(root1!=root2)
        {
            tree[root1]=root2;
            num--;
        }
    }
    cout<<num;
    return 0;
}

接下来就放我那个超时(因为超时也不知道运行的结果对不对,反正样例过了就是过了对吧hhh,其实还过了一个点,第二个点就TLE了)的代码吧,做个对比吧。(其实是辛苦写出来的不想删)

#include <iostream>
#include<queue>
using namespace std;
int room[1000][1000];
bool code[1000000];
bool v[100001];
struct dir{int x,y;}a[100001];
int m,n,k;
void bfs(int dx,int dy)
{
    dir start;
    queue<dir> q;
    start.x=dx;
    start.y=dy;
    q.push(start);
    while(!q.empty())
    {
        start=q.front();
        q.pop();
        for(int j=1;j<=k;j++)
        {
            if(!v[j])
            {
                if(start.x==a[j].x||start.x==a[j].y||start.y==a[j].x||start.y==a[j].y)
                {
                    v[j]=true;
                    q.push(a[j]);
                    code[a[j].x]=true;
                    code[a[j].y]=true;
                }
            }
        }
    }
}
int main()
{
    cin>>m>>n;
    int num=1,cnt=0;
    for(int i=0;i<m;i++)
        for(int j=0;j<n;j++)
        {
            room[i][j]=num;
            num++;
        }
    cin>>k;
    for(int i=1;i<=k;i++)
        cin>>a[i].x>>a[i].y;
    for(int i=1;i<=k;i++)
    {
        if(!v[i])
        {
            v[i]=true;
            bfs(a[i].x,a[i].y);
            code[a[i].x]=true;
            code[a[i].y]=true;
            cnt++;
        }
    }
    for(int i=1;i<num;i++)
        if(!code[i])
            cnt++;
        cout<<cnt;
    return 0;
}

 

o
粉丝 0
博文 500
码字总数 0
作品 0
私信 提问
加载中
请先登录后再评论。

暂无文章

pycurl libcurl link-time ssl backend (nss)

pip uninstall pycurlecho 'pycurl==7.19.5.1 --global-option="--with-nss"' > requires.pypip install -r requires.py...

小红手
23分钟前
17
0
计算机网络性能衡量

1、速率 单位时间(s)内传输信息(bit)量 单位:KB/s, MB/s, Gb/s K = 10^3 ,M = 10^6, G=10^9 一般表示的是理想的传输速率 2、带宽 计算机网络中的带宽和通信等领域的带宽概念不一样,计算机网...

osc_np3y0rbq
23分钟前
3
0
互联网掀起农家乐,巨头上演AI掘金战

配图来自Canva **前有网易、阿里AI养猪,后有腾讯AI养鹅,互联网大佬们纷纷玩起了“农家乐”,互联网的生意在尖端技术的引领之下频频跨界,巨头之间的较量也从线上延伸至线下。**自古“民以食...

osc_5cok9i01
25分钟前
9
0
原来!我在4年前就开始体验雾游戏了!

前有云游戏后有雾游戏,游戏的方式看来起来越来越多种多样。那么“震撼业界”的雾游戏到底是什么来头?它依靠什么改变游戏界?它的原理又是什么? 本月月初,著名的日本游戏杂志《Fami通》表...

osc_j34n26zn
26分钟前
11
0
活动预告|田溯宁与你相约GSMA Thrive·万物生晖,分享5G风口下的创新与投资洞察

在万物互联的时代背景下,5G+AI+IoT的技术变革与融合,正在引发一场深刻的全产业创新与变革。5G技术创新、行业应用及投资机遇已成为科技行业所瞩目的焦点。 6月30日,宽带资本董事长田溯宁将...

osc_0qnrwmy3
27分钟前
7
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部