# A Bug's Life, and check

### Content: bedbugs are crazy

Professor hope studies the sexual orientation of bedbugs. Before the experiment, he figured out the sex of n bedbugs and marked the number on their backs
Word number (1-N). Now pair a batch of bedbugs to see if they are gay.
Input description
The first line is the integer C, followed by c test cases.
The first line of each test case is the number of bedbugs n (12000), and the number of pairs m (110 ^ 6). Next
The row of is the number of m pairs of bedbugs
Output description
There are c lines in total, and each line prints "testcase i: no homosexuality found", or "testcase i: homosexuality found"
sample input
2
3 3
1 2
2 3
1 3
4 2
1 2
3 4

###### sample output

testcase 1: Discovering homosexuality
testcase 2: no homosexuality found
It took me a long time, and the simple application of the search set should be, but it still went around, and the search set should make the same sex become a group, so we should open an array to store its objects, and finally we can't use cin, cout, change to c to be able to pass the school oj

```#include<iostream>
#include<cstdio>
#include<vector>
#include<cstring>
#define lowbit(x) ((x)&(-x))
#define maxn 100005
using namespace std;

int pre;
int l;//For storing objects
int t, n, m;
void init(int a)
{
for (int i = 1; i <= a; i++)
pre[i] = i;
}

int find(int a)
{
if (pre[a] == a)
return a;
return pre[a] = find(pre[a]);
}

void unit(int a, int b)
{
if (find(a) != find(b))
pre[a] = b;
}

int main()
{
scanf("%d", &t);
int k = 0;
while (t--)
{
scanf("%d %d", &n, &m);
init(n);
int a, b;
bool flag = false;
for (int i = 0; i < m; i++)
{
scanf("%d %d", &a, &b);
if (flag) continue;
if (!l[a] && !l[b])
{
l[a] = b;
l[b] = a;
}
else if (l[a] && !l[b]) l[b] = a, unit(b, l[a]);//If two bedbugs have no objects, they are opposite to each other
else if (!l[a] && l[b]) l[a] = b, unit(a, l[b]);//If one of them has an object, then the new object and the original one are the same sex. It is necessary to merge and query the set
else unit(l[a], b), unit(a, l[b]);
if (find(a) == find(b)) flag = true;
}
printf("testcase %d:", ++k);
if (flag)
printf("Discovery of homosexuality\n");
else
printf("No homosexuality found\n");
}
}
```

Added by Quinton1337 on Thu, 14 Nov 2019 16:44:54 +0200