求助一道算法题。

[letianqiu]

题目：
一共有 N 个 cricket team 和 N 个朋友，N 个朋友分别支持这 N 个 team 中的一些队伍（可以都不支持）。你并不知道每个朋友具体支持什么队伍。有函数 support （ friend，team ）返回朋友是否支持队伍。现在你希望选出你的支持队伍（可以不支持任何队伍），但是不能和任何一个朋友支持的队伍完全相同，并且要尽量少调用 support 函数

我目前的思路是对于每个朋友，遍历 team，找到第一个他不支持的队伍，把这个队伍加入我支持的队伍 list 然后跳出，继续询问下一个朋友。不知道这个思路是否有错误，以及有没有更佳的算法

[unavph]

给个看 N 次的：取对角线然后按位取反，这样得到的结果和第 i 个朋友的第 i 位总是不同的。

[unavph]

@unavph 没有更好的结果了，任何查询小于 N 次的算法都会对至少一个朋友的情况完全不知情。这样的话会有至少一个朋友的支持队伍是任意值，也就可能和自己结果重复。

[qiuyk]

想了一下，对是否支持 team 建立二叉决策树，支持往左不支持往右。原问题就变成了找叶节点到根节点不与其他朋友重合的简单路径。应该是可以用 BFS 加剪枝做，不过暂时没想到要怎么剪枝。

[enenaaa]

楼主的思路有问题。 按这个思路，如果第一个朋友支持 0 个 team， 后面人支持 N 个，结果为 N 个，这明显是错的。

在不考虑优化时， 需遍历所有朋友的支持情况，即 N*N 次函数调用。

注意到题目只要求任一不同路径，实际上并不一定要完全遍历。 如 @qiuyk 所说， 可以构建二叉树来搜索。

我的思路，步骤：
1. 对 N 个 team 编号为 t1~ tn。
2. 以 t1 为二叉树根节点。设 ti=t1
3. 遍历 所有的朋友， 如果有人支持 ti， 则为当前层次的所有节点创建左子节点。 如果有人不支持 ti， 则为当前层次所有节点建立右子节点。
4. 遍历本层所有节点， 如果有子节点少于 2 个节点。 即当前路径与所有朋友都不同，回溯路径即为结果。如果是完全二叉树， 则 ti = ti+1。从第 3 步继续执行。

这个算法只有最坏时才需要 N*N 次 support 调用。

[clavichord93]

@unavph 应该没问题，初步想了一下也是这么做

[enenaaa]

额， 将楼主的解法看错了。