poj-2492

//16852K    6313MS  G++ 

 #include <cstdio> 

 #include <queue> 

 #include <cstring> 


 using namespace std; 


 #define MAX 2010 


 char interactionReleation[MAX][MAX]; 

 char interactionCheckFlag[MAX][MAX]; 


 char genderInfo[MAX]; // the gender of bug 0, not checked, 1 male /-1 female 

 char bugCheckFlag[MAX]; 


 struct Bug { 

     char gender; // 0, not checked, 1 /-1 assume bug1 gender is 1(-1 is oK too, just need the difference of gender) 

     int bugId; 

 }; 


 typedef struct Bug Bug; 


 queue<Bug> bugQueue; 


 int bugNum; 

 int interactionNum; 


 char BFS(int beginBug) { 

     while(bugQueue.size()) { 

         bugQueue.pop(); 

     } 


     Bug bug1; 

     bug1.gender = 1; 

     bug1.bugId = beginBug; 

     bugQueue.push(bug1); 

     genderInfo[beginBug] = 1; 

     bugCheckFlag[beginBug] = 1; 


     while(bugQueue.size()) { 

         Bug curBug = bugQueue.front(); 

         int curBugId = curBug.bugId; 

         int curBugGender = curBug.gender; 

          

         bugQueue.pop(); 

         for (int i = 1; i <= bugNum; i++) { // check the bugs interact with cur bug 

             // if this bug interact with curBug 

             if (interactionReleation[curBugId][i] && 

                 !interactionCheckFlag[curBugId][i] && 

                 !interactionCheckFlag[i][curBugId]) { 

                 interactionCheckFlag[curBugId][i] = 1; // this interact has been checked 

                 interactionCheckFlag[i][curBugId] = 1; // this interact has been checked 

                 bugCheckFlag[i] = 1; 

                 if (genderInfo[i] == 0)  {// this bug is not checked yet 

                     genderInfo[i] = -curBugGender; // interact, must be reverse gender 

                 } else if (genderInfo[i] == curBugGender) { // homosexual! 

                     return 1; 

                 } 

                 Bug nextBug; 

                 nextBug.gender = genderInfo[i]; 

                 nextBug.bugId = i; 

                 bugQueue.push(nextBug); 

             } 

         } 

     } 

     return 0; 

 } 


 char checkBugs() { 

     for (int i = 1; i <= bugNum; i++) { 

         if (!bugCheckFlag[i]) {// if not checked 

             if (BFS(i)) { // if 

                 return 1; 

             } 

         } 

     } 

     return 0; 

 } 


 int main() { 

     int caseNum; 

     scanf("%d", &caseNum); 

     for (int i = 0; i < caseNum; i++) { 

         memset(interactionReleation, 0, sizeof(interactionReleation)); 

         memset(interactionCheckFlag, 0, sizeof(interactionCheckFlag)); 

         memset(genderInfo, 0, sizeof(genderInfo)); 

         memset(bugCheckFlag, 0, sizeof(bugCheckFlag)); 

         bugNum = 0; 

         interactionNum = 0; 

         scanf("%d %d", &bugNum, &interactionNum); 

         for (int j = 0; j < interactionNum; j++) { 

             int bug1, bug2; 

             scanf("%d %d", &bug1, &bug2); 

             interactionReleation[bug1][bug2] = 1; 

             interactionReleation[bug2][bug1] = 1; 

         } 

         printf("Scenario #%d:\n", i+1); 

         if (!checkBugs()) { 

             printf("No suspicious bugs found!\n\n"); 

         } else { 

             printf("Suspicious bugs found!\n\n"); 

         } 

     } 
}

16852K    6313MS  G++.... 

速度很慢，这道题好的解法其实是并查集，不过因为做这道题时，分类是搜索，因此就用了BFS, 时间就不care了。

题目要求找到的是是否有同性恋bug,

判断的标准就是，同样gender的bug交配了，那么就必然有同性恋蟑螂。

用BFS的思路，就是现从某一个bug作为第一个节点开始进行广度遍历，为第一个bug指定一个gender（公母都无所谓，因为是彼此对称的），

然后其相邻的节点（也就是与此bug交配的其他bug）的gender就应该是此相反的gender，

要注意的是，一般的BFS是遍历所有的节点，而本体则要求遍历所有的边（因为我们check的是bug之间的交配，就是bug之间的边），

所以相应的flag二维矩阵就要存储每个边是否被遍历过，

在从某个节点遍历其他的节点时，即从一个bug(A)考察与它交配的其他bug(B)时，

会有3个case：

case1： B节点是第一次被遍历到，那么B的gender就置为A的相反gender

case2:  B在之前已经通过其他bug的交配关系（即其他的边）被遍历过，B的gender与A的gender相反，这是正确的情况，继续遍历边即可。

case3: 同case2，但是B的gender与A的gender一样，那么A与B中必有同性恋bug，直接return 退出BFS 输出结果即可。

要注意的几点：

1.搞一个数组来保存bug的gender，这样才能在需要的时候根据bug的id取得其gender

2. 要注意，不一定只有一个图，而是可能会有好几个独立的连通图，对每个图都要bfs

比如：

5个bug

1-2

3-.4

4-5

3-5

1和2组成一个独立图， 3,4,5组成一个独立图

要对每个连通图进行check，只有每个图都没有同性恋，才算完全没有。

因此要搞一个flag数组标示某个bug是否被check过，一直对没有被check过的bug进行上面的check，直到所有的bug都被check过了。

这道题本质就是遍历+染色，只不过这里要判断染色冲突，染色规则也是特定的(相邻节点颜色相反).