（并查集建立关系）Parity game -- POJ -1733-白红宇

强烈建议你试试无所不能的chatGPT，快点击我

（并查集建立关系）Parity game -- POJ -1733

阅读量：5157 次

发布时间：2019-06-13

本文共 959 字，大约阅读时间需要 3 分钟。

链接：

http://poj.org/problem?id=1733

http://acm.hust.edu.cn/vjudge/contest/view.action?cid=82830#problem/H

代码：

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            using namespace std;#define N 110#define oo 0xfffffffmap
             
              f; ///f[i]=x, i是int类型的，x也是int类型的map
              
               r;int n, m;int Find(int x){ if(!f[x]) return x; int k=f[x]; f[x]=Find(f[x]); r[x]=(r[x]+r[k])%2; return f[x];}int main(){ while(scanf("%d", &n)!=EOF) { scanf("%d", &m); int i, a, b, fa, fb, ans=0, flag=0; char s[N]; for(i=1; i<=m; i++) { int num=0; scanf("%d%d%s", &a, &b, s); a--; if(strcmp(s, "odd")==0) num=1; fa=Find(a), fb=Find(b); if((a<0 || a>=n) || (fa==fb && (r[a]+num)%2!=r[b])) flag=1; if(flag==1) continue; if(fa!=fb) { f[fa]=fb; r[fa]=(r[b]-(r[a]+num)%2+2)%2; } ans++; } printf("%d\n", ans); } return 0;}

转载于:https://www.cnblogs.com/YY56/p/4735734.html

你可能感兴趣的文章

Hibernate主键生成策略

Crushing Machinery - Strong Support of Cement Enterprise

Django框架（十九）—— drf：序列化组件（serializer）

JS一些概念知识及参考链接

关于JS中&&和||用法技巧

suoi14 子树查找 (dfs)

[转] Java se 7新特性研究(二)

移动端开发模式

Androidの高级交互之仿微信摇一摇(真心摇一摇，而不是像网传的就那么简单的震动一下)...

Java基础知识强化之IO流笔记39：字符流缓冲流之复制文本文件案例01

Java基础知识强化48：Java中哈希码

TCP/IP协议原理与应用笔记24：网际协议（IP）之 IP协议的简介

C#中Enum用法小结

ORA-12541:TNS:无监听程序

Cocos2d-x动作学习笔记分类： cocos2d代码编写 ...

第4章例4-12 源程序2

Bootstrap 3 How-To #1 下载与配置

喝酒易醉，品茶养心，人生如梦，品茶悟道，何以解忧？唯有杜康！-- 愿君每日到此一游！

当前时间: 2024-11-20 07:30:59 当前IP: 3.133.120.91 联系邮箱:javaeecc@qq.com Copyright © 2020 - 2022 baihongyu.com 京ICP备2021015314号-2

强烈建议你试试无所不能的CHAT-GPT，快点击我

强烈建议你试试无所不能的CHAT-GPT，快点击我