文档章节

poj_2492/hdoj_1829_A Bug's Life并查集

電泡泡
 電泡泡
发布于 2013/10/10 17:25
字数 170
阅读 15
收藏 0
#include<cstdio>
#define N 2005
using namespace std;
int f[N],rank[N], n, k;
bool flag;

inline void init(){
    flag=false;
    for(int i=0; i<=n; ++i)
        f[i]=i, rank[i]=0;
}
int find(int x){
    if(x==f[x])return f[x];
    int t=find(f[x]);
    rank[x] = (rank[f[x]]+rank[x])&1;
    f[x]=t;
    return f[x];
}
void Union(int x, int y){
    int a=find(x), b=find(y);
    if(a==b){
        if(rank[x]==rank[y])
            flag=true;
        return;
    }
    f[a]=b;
    rank[a] = (rank[x]+rank[y]+1)&1;
}


int main(){
    int T,a,b,cas=1;
    scanf("%d",&T);
    while(T--){
        scanf("%d%d",&n,&k);
        init();
        for(int i=0; i<k; ++i){
            scanf("%d%d",&a,&b);
            if(flag)continue;
            Union(a,b);
        }
        printf("Scenario #%d:\n",cas++);
        if(flag)printf("Suspicious bugs found!\n");
        else printf("No suspicious bugs found!\n");
        printf("\n");
    }
    return 0;
}

© 著作权归作者所有

共有 人打赏支持
電泡泡
粉丝 24
博文 183
码字总数 69717
作品 0
衡阳
私信 提问
算法进阶路径

第一阶段:练经典常用算法,下面的每个算法给我打上十到二十遍,同时自己精简代码, 因为太常用,所以要练到写时不用想,10-15分钟内打完,甚至关掉显示器都可以把程序打 出来. 1.最短路(Fl...

暖冰
2016/04/02
82
1
一个搞ACM需要掌握的算法

ACM的竞赛性强,因此自己应该和自己的实际应用联系起来.适合自己的才是好的,有的人不适合搞算法,喜欢系统架构,因此不要看到别人什么就眼红,发挥自己的长处,这才是重要的. 第一阶段:练经典常用...

long0404
2015/06/24
0
0
简明刷题指南

Cover 1. 刷题网站 HDUOJ HDOJ Welcome To PKU JudgeOnline POJ PAT image.png Codeforces CodeForces AtCoder Atcoder Virtual Judge Vjudge 2. 刷题步骤 以HDUOJ为例 首先注册网站账号 点击......

SpiffyEight77
01/06
0
0
POJ ~ 1182 ~ 食物链 (带权并查集)

参考博客:POJ-1182 食物链 思路:经典的带权并查集。除了并查集那个数组外,多开一个权值数组,或者把两个合成一个结构体数组。权值为每个点与根节点的关系//0:同类 1:吃 2:被吃。 图一:路...

ZscDst
01/18
0
0
HDOJ 1811 Rank of Tetris

Rank of TetrisTime Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 11206 Accepted Submission(s): 3206 Problem Description 自从L......

dear_jia
04/18
0
0

没有更多内容

加载失败,请刷新页面

加载更多

Spring Security 实现 antMatchers 配置路径的动态获取

1. 为什么要实现动态的获取 antMatchers 配置的数据 这两天由于公司项目的需求,对 spring security 的应用过程中需要实现动态的获取 antMatchers ,permitAll , hasAnyRole , hasIpAddre...

大木老师故事的小黄花
15分钟前
14
0
Java 内存模型

一、Java内存模型 硬件处理 电脑硬件,我们知道有用于计算的cpu、辅助运算的内存、以及硬盘还有进行数据传输的数据总线。在程序执行中很多都是内存计算,cpu为了更快的进行计算会有高速缓存,...

微笑向暖wx
15分钟前
0
0
Maven shade的使用

有时你的工程里会和你的Spark环境出现包冲突,这时候可以用Maven shade将你的包名重命名,在maven里加上: <plugin> <groupId>org.apache.maven.plugins</groupId> <artifactId>maven-shade......

守望者之父
16分钟前
0
0
SpringBoot中导入Excel的总结

1 先导入配置文件 <dependency><groupId>org.apache.poi</groupId><artifactId>poi</artifactId></dependency><dependency><groupId>org.apache.poi</groupI......

小小小施爷
16分钟前
0
0
python是如何进行内存管理的

Python引入了一个机制:引用计数。 python内部使用引用计数,来保持追踪内存中的对象,Python内部记录了对象有多少个引用,即引用计数,当对象被创建时就创建了一个引用计数,当对象不再需要...

糖宝lsh
19分钟前
0
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部