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[100000]; int l[100000];//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"); } }