题意 : 给你 n 只虫且性别只有公母, 接下来给出 m 个关系, 这 m 个关系中都是代表这两只虫能够交配, 就是默认异性, 问你在给出的关系中有没有与异性交配这一事实相反的, 即同性之间给出了交配关系。
分析 : 本题雷同POJ 1182 食物链, 如果会了那一题, 那现在这题便简单多了, 建议先了解食物链的偏移向量做法。这里也是使用向量的思考方式来进行relation的变化, 这里我令 relation = 0为同性, relation = 1为异性, 接下来的步骤就和食物链的雷同了。
优化 :
① 因为关系的值只有0 或 1, 这里可以考虑位运算中的异或来加快relation变化的运算。
② 由于给出的输入很多, 所以可以采用读入挂来加快读入速度。
瞎搞 : 一开始计算关系的时候居然去%1, 失策啊, 要将范围控制在[0, n]之间的话就应该%(n+1)。还有在判断是否矛盾时候, 实际只要判断两个虫的relation是否一样即可, 我还在加减乘除模来模去=_=
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<iostream>
using namespace std;
;
int f[maxn], relation[maxn], n, num;
inline int Scan()
{
, ch;
bool flag = false;
if((ch=getchar()) == '-') flag = true;
';
+ch-';
return flag?-res:res;
}
inline void initialize()
{
; i<=n; i++){
relation[i] = ;
f[i] = i;
}
}
int findset(int x)
{
if(f[x] == x) return x;
int father = f[x];
f[x] = findset(father);
relation[x] = relation[father]^relation[x];
//同 relation[x] = ( relation[father] + relation[x] )%2;
return f[x];
}
int main(void)
{
int nCase;
nCase = Scan();
;
while(nCase--){
bool flag = true;
n = Scan(); num = Scan();
initialize();
while(num--){
int a, b;
a = Scan(); b = Scan();
if(!flag) continue;
if(a==b){
flag = false;
continue;
}
int root_a = findset(a);
int root_b = findset(b);
if(root_a != root_b){
f[root_b] = root_a;
relation[root_b] = relation[a]^^(-relation[b]);
//同 relation[root_b] = ( relation[a] + 1 - relation[b] )%2;
}else{
if(relation[a]==relation[b]) flag = false;
//同 if( (-relation[a]+relation[b]+2)%2 != 1) flag = false;
}
}
if(!flag){
printf("Scenario #%d:\nSuspicious bugs found!\n", ++t);
}else{
printf("Scenario #%d:\nNo suspicious bugs found!\n", ++t);
}
puts("");
}
;
}