1. There are two types of professional wrestlers: "good guys" and "bad guys." Between any pair
of professional wrestlers, there may or may not be a rivalry. Suppose we have n professional
wrestlers and we have a list of r pairs of wrestlers for which there are rivalries. Give an O(n +
r)-time algorithm that determines whether it is possible to designate some of the wrestlers as
good guys and the remainder as bad guys such that each rivalry is between a good guy and a
bad guy. If is it possible to perform such a designation, your algorithm should produce it.
这个月太忙,都没时间写博客
刚写了离散作业,实际是BFS的变体
直接上代码
bool Graph::designation(int s){
initBFS();
graNodes[s].color=GRAY;
graNodes[s].level=0;
deque<Node*> blocks;
blocks.clear();
blocks.push_back(&graNodes[s]);
Node* tempNode;
while(!blocks.empty()){
tempNode=blocks.front();
blocks.pop_front();
cout<<"*"<<tempNode->nodeID<<"*";
for (vector<Node*>::iterator ivl = (tempNode->adjList).begin(); ivl != (tempNode->adjList).end(); ivl++) {
if(((*ivl)->color)!=WHITE){
if(((*ivl)->level%2)==(tempNode->level%2)){
cout<<"节点"<<(*ivl)->nodeID<<"和节点"<<(tempNode->nodeID)<<"不能满足条件"<<endl;
return false;
}
}
else{
(*ivl)->color=GRAY;
(*ivl)->level=tempNode->level+1;
(*ivl)->pre=tempNode->nodeID;
blocks.push_back(*ivl);
}
}
tempNode->color=BLACK;
}
return true;
}