首页 > 代码库 > HDU 1829 A Bug's Life
HDU 1829 A Bug's Life
https://vjudge.net/problem/HDU-1829
题意:
有一堆bug,给出他们的配对关系,问他们之间是否有可能存在同性恋的行为。
思路:
简单并查集,与食物链那题的思路比较像。每一次输入的两个数,定为a和b,每次将a和b+2000合并,将a+2000和b合并,表示他们是异性关系,一旦出现a和b同根,那么就是同性关系。
代码:
1 #include <stdio.h> 2 #include <string.h> 3 4 int par[4005]; 5 6 void init(int n) 7 { 8 for (int i = 1;i <= n;i++) 9 { 10 par[i] = i; 11 } 12 } 13 14 int fin(int x) 15 { 16 if (x == par[x]) return x; 17 else return par[x] = fin(par[x]); 18 } 19 20 void unit(int x,int y) 21 { 22 x = fin(x); 23 y = fin(y); 24 25 if (x != y) par[x] = y; 26 } 27 28 int main() 29 { 30 int t; 31 int cas = 0; 32 scanf("%d",&t); 33 34 while (t--) 35 { 36 printf("Scenario #%d:\n",++cas); 37 38 int n,m; 39 40 scanf("%d%d",&n,&m); 41 42 init(n+2000); 43 44 bool f = 0; 45 46 for (int i = 0;i < m;i++) 47 { 48 int a,b; 49 50 scanf("%d%d",&a,&b); 51 52 if (fin(a) == fin(b)) f = 1; 53 else 54 { 55 unit(a+2000,b); 56 unit(a,b+2000); 57 } 58 } 59 60 if (f) printf("Suspicious bugs found!\n\n"); 61 else printf("No suspicious bugs found!\n\n"); 62 } 63 64 return 0; 65 }
HDU 1829 A Bug's Life
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。