文档章节

【codevs 1995】黑魔法师之门

LOI_xczhw
 LOI_xczhw
发布于 2016/10/30 09:57
字数 207
阅读 7
收藏 0

嗯……
通过样例看出来,答案要么不变,要么*2+1
然后
发现如果新加的这条边same(l[i].f,l[i].t),就*2+1
证明以后再说,机房要关门了……

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
const int MAXN = 200000 + 5;
const int P = 1000000009;
int n,m,p;
int fa[MAXN];
int rank[MAXN];
void init()
{
    for(int i = 0;i <= n;i ++)
        fa[i] = i;
    memset(rank,0,sizeof(rank));
    return;
}
int find(int x)
{
    return fa[x] == x ? x : fa[x] = find(fa[x]);
}
void merge(int x,int y)
{
    x = find(x);
    y = find(y);
    if(x == y)
        return;
    if(rank[x] > rank[y])
        swap(x,y);
    fa[x] = y;
    if(rank[x] == rank[y])
        rank[y] ++;
    return;
}
bool same(int x,int y)
{
    return find(x) == find(y);
}
int f,t;
int k;
int main()
{
    scanf("%d %d",&n,&m);
    init();
    while(m --)
    {
        scanf("%d %d",&f,&t);
        if(same(f,t))
            k = (k << 1) + 1,k %= P;
        printf("%d\n",k);
        merge(f,t);
    }
    return 0;
}

© 著作权归作者所有

LOI_xczhw
粉丝 1
博文 79
码字总数 42567
作品 0
莱芜
私信 提问
2018 蓝桥杯省赛 B 组模拟赛(一)封印之门(最短路)

版权声明:转载请告知博主并要注明出处嗷~ https://blog.csdn.net/AkatsukiItachi/article/details/88723933 题目链接 蒜头君被暗黑军团包围在一座岛上,所有通往近卫军团的路都有暗黑军团把...

语海与冰
03/21
0
0
关于正则的提取

酷书包每日推荐 1完美世界 2武炼巅峰 3大主宰 4儒道至圣 5官道无疆 6雪鹰领主 7我真是大明星 8夜天子 9星战风暴 10超品相师 11校花的贴身高手 12一剑飞仙 13黑铁之堡 14玄界之门 15大明武夫 ...

小怪兽你一点也不乖
2017/03/19
48
1
英国书商发掘下一个"哈里波特"

因为出版《哈里波特》系列小说而备受瞩目的英国Bloomsbury公司,正在准备将它传奇性的成功继续下去。 这次它选择的目标是44岁的女作家克拉克的首部作品《斯特兰奇和诺雷尔》(Jonathan Stra...

阮一峰
2004/04/01
0
0
splay的各种操作与简易讲解

基本操作 插入 和二叉查找树一样,但是插入完成后要splay一下(即伸展),伸展操作下面有 伸展 查找前驱或后驱 例题:codevs1285/洛谷P2286/bzoj1208 宠物收养所 删除和合并 先把要删除的点s...

litble
2017/07/07
0
0
PromiseClass 0.9.5 发布,Promise 黑魔法

回调恶魔 在目前Javascript技术背景下,当碰到大量异步代码时,会非常头痛。 目前有以下几种手段来解决异步回调问题: 传统异步回调 Promise ES6 Generator ES7 async 远古 对于异步回调,相...

YanisWang
2015/11/11
1K
6

没有更多内容

加载失败,请刷新页面

加载更多

PHP计算两个经纬度地点之间的距离

/** * 求两个已知经纬度之间的距离,单位为米 * * @param lng1 $ ,lng2 经度 * @param lat1 $ ,lat2 纬度 * @return float 距离,单位米 * @author www.Alixixi.com */function get...

子枫Eric
22分钟前
14
0
Linux—day 4

ch2 需要掌握的命令 (1)cat -n 1.txt (2)more 1.txt (3)head -n 15 initial-setup-ks.cfg (4)tail -n 17 initial-setup-ks.cfg;tail -f initial-setup-ks.cfg (5)cat -n anaconda-ks.c......

呵呵暖茶
35分钟前
16
0
【Kubernetes社区之路】我的PR被抢了

2019年11月的某天,我无意间发现一个PR作者在自己的PR中抱怨自己的PR没被合入,而另一个比自己提交晚且内容几乎一样的PR则被合入了。 字里行间透露些许伤感外加无奈: 作为一名开源爱好者,我...

恋恋美食
41分钟前
21
0
阻塞队列

对于许多线程问题, 可以通过使用一个或多个队列以优雅且安全的方式将其形式化。生产者线程向队列插人元素, 消费者线程则取出它们。 使用队列, 可以安全地从一个线程向另 一个线程传递数据...

ytuan996
43分钟前
23
0
mysql docker 配置

安装   主机上的mysql服务是基于docker安装的,具体安装脚本如下: docker run --detach \--restart always \--publish 3306:3306 --name mysql \--volume /data/mysql/logs:/logs \-...

qwfys
46分钟前
18
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部