来自谷歌的算法问题：
一位老师想把他的问题学生分成两组。他有一个名字列表（成对），代表不能归入同一组的学生。我们的任务是检查是否有可能将所有学生分开而不发生碰撞。
例如，如果列表是：
Jack Jim (cannot be in the same group)
Jim Rose (...)
Rose Jack (...)
那么不可能在没有碰撞的情况下将它们全部分开。
我的想法是利用图的思想，用关联数组或映射来实现。但是，我认为如果图中不连通的分支很多，那会很复杂。任何人都可以帮忙吗？
问问题
254 次
4 回答
1
这听起来像是一个图形着色问题。首先声明杰克属于“黑色”组。这意味着吉姆必须在“红色”组中。这意味着“玫瑰”必须在“黑色组”中。现在我们得到了碰撞：因为玫瑰是“黑色”，所以杰克必须是“红色”，但我们已经为他分配了黑色。
编辑：用于实现的伪代码（我还没有编译它，我知道它会泄漏内存）
enum Group {
UNKNOWN,
RED,
BLACK
};
struct Person
{
string name;
Group group;
set<Person*> exclusionList;
}
class Class
{
public:
void addExclusion(const string& inPersonA, const string& inPersonB)
{
bool first = (mMembers.empty());
Person* personA = findPerson(inPersonA);
Person* personB = findPerson(inPersonB);
personA->exclusinList.insert(personB);
personB->exclusionList.insert(personA);
if (first) {
// special case, assign initial colors
personA->color = BLACK;
personB->color = RED;
} else {
switch (personA->color) {
case UNKNOWN:
switch(personB->color) {
case UNKNOWN:
break; // we can't do anything, nothing is known
case BLACK:
setColor(personA, RED);
break;
case RED:
setColor(personA, BLACK);
break;
}
break;
case RED:
switch (personB->color) {
case UNKNOWN:
setColor(personB, BLACK);
break;
case RED:
throw "EXCLUSION FAILURE";
case BLACK:
break;
}
case BLACK:
switch (personB->color) {
case UNKNOWN:
setColor(personB, BLACK);
break;
case RED:
break;
case BLACK:
throw "EXCLUSION FAILURE";
}
}
}
}
private:
Person* findPerson(const string& inString)
{
Person* rval = mMembers[inString];
if (rval == null) {
rval = new Person(inString, UNKNOWN);
mMembers[inString] = rval;
}
return rval;
}
void setColor(Person* inPerson, Group inColor)
{
if (inPerson->color == inColor)
return; // no op
if (inPerson->color != UNKNOWN && inPerson->color != inColor)
throw "EXCLUSION FAILURE";
// now we know inPerson was UNKNOWN
inPerson->color = inColor;
for (auto iter = inPerson->exclusionList.begin(); iter != inPerson->exclusionList.end(); ++iter) {
setColor(*iter, (inColor == RED) ? BLACK : RED);
}
unordered_map<string, Person*> mMembers;
};
于 2013-09-16T04:48:18.950 回答
0
#algorithm.coffee
#teacher wants to separate his/her problem prisoners into two groups by keeping
#separated certain individuals. we have a list of kids and need to decide how to
#separate them according to rules provided. only two groups allowed apparently. if
#more are required we are in collision situation.
reset = '\x1B[0m'
red = '\x1B[0;31m'
green = '\x1B[0;32m'
#we list all the kids, and such that the values are arrays holding all problems associated with that
# key=kid
contras =
"abe": []
"billy": []
"bella": []
"charles": []
"dafner": []
"echo": []
"ferris": []
"gomer": []
"gina": []
"heloise": []
#we have empty groups
group1 = []
group2 = []
# defining problem relationships
problems = [
["abe", "heloise"]
["bella", "dafner"]
["gomer", "echo"]
#["abe", "bella"]
["heloise", "dafner"]
["echo", "ferris"]
["abe", "dafner"]
]
# with the problems array we can populate the contras object
for item in problems
contras[item[0]].push item[1]
contras[item[1]].push item[0]
# with the populated contras object we can determine conflicts
for key, value of contras
for item in value
for item2 in value
for item3 in contras[item]
if item2 == item3 and item3 != item
console.log red + "There is a collision implicit in problem pair " + reset + key + red + " and " + reset + item + red + " because both " + reset + key + red + " and " + reset + item + red + " are problematic with " + reset + item3 + red + " who is also known as " + reset + item2 + red + ".\n"
# if there are no unresolvable conflicts then this routine below
# will work, otherwise you'll see a bunch of
# red flags thrown by the routine above.
for item in problems
if group1.length == 0
group1.push item[0]
group2.push item[1]
else
duplicate = false
for item2 in group1
if item2 in contras[item[0]] then duplicate = true
if duplicate == true
group1.push item[1] unless item[1] in group1
group2.push item[0] unless item[0] in group2
else
group1.push item[0] unless item[0] in group1
group2.push item[1] unless item[1] in group2
### some tests
# checking if group1 contains problems
for item in group1
for item2 in problems
for item3 in item2
if item == item3
for item4 in item2
if item4 != item
for item5 in group1
if item4 == item5
duplicate = false
for item6 in collisions
if item2 == item6 then duplicate = true
if duplicate == false
collisions.push item2
# checking if group2 contains problems
for item in group2
for item2 in problems
for item3 in item2
if item == item3
for item4 in item2
if item4 != item
for item5 in group2
if item4 == item5
duplicate = false
for item6 in collisions
if item2 == item6 then duplicate = true
if duplicate == false
collisions.push item2
###
console.log green + "whole kids group is " + reset + kids
console.log green + "group1 is " +reset + group1
console.log green + "group2 is " + reset + group2
# console.log red + "collisions are " + reset + collisions
于 2013-09-16T06:10:52.047 回答
0
您需要做的就是检查您的图是否是二分图（即，您的图的顶点是否能够被分配两种颜色中的一种，使得没有边连接相同颜色的顶点）。如果你用整数给班上的学生编号：
1. Jack
2. Jim
3. Rose
您可以使用 C++ 中的 Boost Graph Library 轻松解决此问题：
#include <iostream>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/bipartite.hpp>
using namespace boost;
int main (int argc, char **argv)
{
typedef adjacency_list <vecS, vecS, undirectedS> vector_graph_t;
typedef std::pair <int, int> E;
E edges[] = { E (1, 2), E (2, 3), E (3, 1)};
vector_graph_t students (&edges[0],&edges[0] + sizeof(edges) / sizeof(E), 3);
if ( is_bipartite(students) )
std::cout << "Bipartite graph" << std::endl;
else
std::cout << "Non bipartite graph" << std::endl;
return 0;
}
于 2013-09-16T06:11:06.997 回答