## A Bug's Life POJ - 2492 转

o
osc_gccs85s0

A Bug's Life

Background
Professor Hopper is researching the sexual behavior of a rare species of bugs. He assumes that they feature two different genders and that they only interact with bugs of the opposite gender. In his experiment, individual bugs and their interactions were easy to identify, because numbers were printed on their backs.
Problem
Given a list of bug interactions, decide whether the experiment supports his assumption of two genders with no homosexual bugs or if it contains some bug interactions that falsify it.

Input

The first line of the input contains the number of scenarios. Each scenario starts with one line giving the number of bugs (at least one, and up to 2000) and the number of interactions (up to 1000000) separated by a single space. In the following lines, each interaction is given in the form of two distinct bug numbers separated by a single space. Bugs are numbered consecutively starting from one.

Output

The output for every scenario is a line containing "Scenario #i:", where i is the number of the scenario starting at 1, followed by one line saying either "No suspicious bugs found!" if the experiment is consistent with his assumption about the bugs' sexual behavior, or "Suspicious bugs found!" if Professor Hopper's assumption is definitely wrong.

`````` 1 #include <iostream>
2 #include <cstdio>
3 #include <algorithm>
4 #include <queue>
5 #include <vector>
6 #include <cmath>
7
8 using namespace std;
9
10 #define ll long long
11 #define pb push_back
12 #define fi first
13 #define se second
14
15 const int N = 2000 << 1;
16 struct node
17 {
18     int rt, v;
19 }fa[N];
20
21 int Find(int x)
22 {
23     if(fa[x].rt == x) return x;
24     else{
25         int tmp = fa[x].rt;
26         fa[x].rt = Find(tmp);
27         fa[x].v = (fa[x].v + fa[tmp].v) % 2;
28         return fa[x].rt;
29     }
30 }
31
32 bool Union(int x, int y)
33 {
34     int fax = Find(x);
35     int fay = Find(y);
36     if(fax != fay){
37         fa[fay].rt = fax;
38         fa[fay].v = (fa[x].v + 1 - fa[y].v) % 2;
39         return true;
40     }else{
41         if(0 == (fa[x].v + 1 - fa[y].v) % 2) return true;
42         else return false;
43     }
44 }
45
46 void solve()
47 {
48     int T;
49     scanf("%d", &T);
50     for(int _case = 1; _case <= T; ++_case){
51         int n, m;
52         scanf("%d%d", &n, &m);
53         for(int i = 0; i <= n; ++i){
54             fa[i].rt = i;
55             fa[i].v = 0;
56         }
57         vector<pair<int ,int > > info;
58         int x, y;
59         for(int i = 1; i <= m; ++i){
60             scanf("%d%d", &x, &y);
61             info.pb({x, y});
62         }
63
64         int error = 0;
65         for(int i = 0; i < m; ++i){
66             x = info[i].fi;
67             y = info[i].se;
68             if(!Union(x, y)){
69                 error = 1;
70                 break;
71             }
72         }
73
74         printf("Scenario #%d:\n", _case);
75         printf("%s\n\n", error == 1 ? "Suspicious bugs found!" : "No suspicious bugs found!");
76     }
77 }
78
79 int main()
80 {
81
82     solve();
83
84     return 0;
85 }``````

o

### osc_gccs85s0

WindsDeng
2012/12/09
2.1K
0

jquery-Lweight-Validate ：轻量级校验框架。之所以这么称呼它。原因很简单，与其他校验框架相比，次框架没有太多的JS代码在你的HTML中，仅仅一行，其他所有的校验属性，均通 过框架中自定义...

2013/05/05
2.8K
3

GMU（Global Mobile UI）是百度前端通用组开发的移动端组件库，具有代码体积小、简单、易用等特点，组件内部处理了很多移动端的bug，覆盖机型广，能大大减少开发交互型组件的工作量，非常适合...

2013/06/03
9.8K
1
jquery对象/标签映射扩展--NickName

jquery对象/标签映射扩展-NickName OTM是什么 以往把这样的一个json对象 var data = {}; data.UserId = "8888"; data.UserName = "赵六"; data.School="湖北工业大学"; data.schoolNo=100002......

2013/06/13
1K
0
monodevelop2.6beta1发布

http://monodevelop.com/,最近在用monodevelop做mvc2的开发，感觉不错，有些方面强过vs2008，不过bug也不少。

2011/03/02
687
0

24分钟前
3
0
Docker镜像加速

vim /etc/docker/daemon.json # 将"registry-mirrors": ["https://......com"] （对应自己的加速地址）复制到文件中 # 重新加载文件和重启dockersudo systemctl daemon-reloadsudo syst......

codeccb
36分钟前
12
0
Android Studio使用lombok

36分钟前
7
0
Stream数据流

Stream类基础操作 从JDK1.8开始提供了java.yitl.stream数据流的开发板，而Stream就是这个包中提供的一个接口，这个接口主要是通过函数式编程结构实现集合数据的分析，所以在Collection接口张...

41分钟前
13
0

fyin1314
54分钟前
6
0