您现在的位置是:首页 > 学习之路 > ACM||算法ACM||算法

POJ 2492 A Bug's Life

2019-07-25【ACM||算法】人已围观

简介POJ 2492 A Bug's Life
题意:
有t组测试数据, 对于每组数据,第一行n, m分别表示昆虫的数目和接下来m行x, y
x, y表示教授判断x, y为异性, 问教授是否有错误判断,即存在x, y为同性;
思路:
种类并查集。
亦可使用扩展域并查集。
注意:
智商税,Union 调用Find 不是par[]!!!!!!!!!!!!!!!!!!!!
脑子是个好东西
后记:
继续交智商税。。。。使用扩展域并查集。U

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <map>

using namespace std;

const int maxn = 2010;
int par[maxn<<1];
int t, m, n;
int flag;

int Find(int x){
    if(par[x] == x)
        return x;
    return par[x] = Find(par[x]);
}

void Union(int x, int y){
    par[Find(x)] = Find(y);
}

void init(){
    flag = 0;
    for(int i = 0; i <= n*2; ++i)
        par[i] = i;
}

int main(){
    scanf("%d", &t);
    for(int T = 1; T <= t; ++T){
        scanf("%d%d", &n, &m);
        init();
        int x, y;
        for(int i = 0; i < m; ++i){
            scanf("%d%d", &x, &y);
            int xx = Find(x);
            int yy = Find(y);
            if(xx == yy)
                flag ++;
            else{
                Union(x, y+n);
                Union(x+n, y);
            }
        }
        if(flag)
            printf("Scenario #%d:\nSuspicious bugs found!\n\n", T);
        else
            printf("Scenario #%d:\nNo suspicious bugs found!\n\n", T);
    }
}
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <map>

using namespace std;

const int maxn = 2010;
int par[maxn<<1];
int d[maxn<<1];
int t, m, n;
map<int,int> mp;
int cot;

int Find(int x){
    if(x != par[x]){
        int k = par[x];
        par[x] = Find(par[x]);
        d[x] ^= d[k];
    }
    return par[x];
}

int flag;

void Union(int x, int y, int v = 1){
    int xx = Find(x);
    int yy = Find(y);
    if(xx != yy){
        par[xx] = yy;
        d[xx] = d[x] ^ d[y] ^ v;
    }
    else{
        if(!d[x] ^ d[y])
            flag ++;
    }
}

void init(){
    mp.clear();
    flag = 0;
    cot = 1;
    for(int i = 0; i <= n*2; ++i){
        par[i] = i;
        d[i] = 0;
    }
}

int main(){
    scanf("%d", &t);
    for(int T = 1; T <= t; ++T){
        scanf("%d%d", &n, &m);
        init();
        int x, y;
        for(int i = 0; i < m; ++i){
            scanf("%d%d", &x, &y);
            if(!mp[x])
                mp[x] = cot++;
            if(!mp[y])
                mp[y] = cot++;
            Union(mp[x], mp[y], 1);
        }
        if(flag)
            printf("Scenario #%d:\nSuspicious bugs found!\n\n", T);
        else
            printf("Scenario #%d:\nNo suspicious bugs found!\n\n", T);
    }
}

Tags:ACM   编程   个人   题解   算法   C|C++

很赞哦! ()

文章评论

站点信息

  • 建站时间:2018-11-25
  • 网站程序:帝国CMS7.5
  • 文章统计:118篇文章
  • 标签管理标签云
  • 统计数据百度统计
  • 网站地图XML网站地图
  • 微信公众号:扫描二维码,关注我的公众号
  • GitHub:扫描二维码,关注我的GitHub

客服在线

QQ客服

客服微信扫码

服务时间

周一至周日 9:00-21:00