我正在为一个算法类编写 ac 项目，我真的需要一些帮助！
问题是：
我有一组像这样的名称 N = (James,John,Robert,Mary,Patricia,Linda Barbara) ，它们存储在 RB 树中。
从这组名字开始，形成了一系列类似的情侣：（
詹姆斯，玛丽）
（詹姆斯、帕特里夏）
（约翰、琳达）
（约翰、芭芭拉）
（罗伯特、琳达）
（罗伯特，芭芭拉）
现在我需要以一种可以形成 n 个子组的方式合并元素，约束条件是尊重每个配对并且该组具有最小可能的基数。
对于示例中的夫妇，他们将分成两组
（詹姆斯、玛丽、帕特里夏）和（约翰、罗伯特、芭芭拉、琳达）。
任务是返回形成的最大组数以及基数最大的组中男性和女性的数量。
在这种情况下，它将是 2 2 2
我正在考虑构建一个图，其中每个名称都由一个顶点表示，并且只有当两个顶点配对时才位于一条边上。
然后我可以使用算法（如 Kruskal）来找到最小生成树。对吗？
问题是图不会完全连接。
我还需要找到一种方法将名称映射到图的边缘，反之亦然。
边可以用字符串索引吗？
非常感谢每一个帮助:)
谢谢指教！
i'm coding a c project for an algorithm class and i really need some help!
Here's the problem:
I have a set of names like this one N = (James,John,Robert,Mary,Patricia,Linda Barbara) wich are stored in an RB tree.
Starting from this set of names a series of couple like those ones are formed:
(James,Mary)
(James,Patricia)
(John,Linda)
(John,Barbara)
(Robert,Linda)
(Robert,Barbara)
Now i need to merge the elements in a way that i can form n subgroups with the constraint that each pairing is respected and the group has the smallest possible cardinality.
With the couples in the example they will form two groups
(James,Mary,Patricia) and (John,Robert,Barbara,Linda).
The task is to return the maximum number of groups formed and the number of males and females in the group with the maximum cardinality.
In this case it would be 2 2 2
I was thinking about building a graph where every name is represented by a vertex and two vertex are in an edge only if they are paired.
I can then use an algorithm (like Kruskal) to find the Minimum spanning tree.Is that right?
The problem is that the graph would not be completely connected.
I also need to find a way to map the names to the edges of the Graph and vice-versa.
Can the edges be indexed by a string?
Every help is really appreciated :)
Thanks in advice!
发布评论
评论（3）
您不需要找到最小生成树。这实际上是为了在图中找到仍保持图连接的“最佳”边。换句话说，你并不关心约翰和罗伯特是如何联系的，只关心他们是这样的。
你说问题在于图不会完全连接，但我认为这实际上是重点。如果您按照建议使用对来表示图边，则连接的顶点将形成您正在查找的组。
在您的示例中，詹姆斯连接到玛丽，詹姆斯也连接到帕特里夏。没有其他人连接到这三个顶点中的任何一个（如果他们这样做了，你就会有另一对包含他们的顶点），这就是为什么他们形成一个组（詹姆斯，玛丽，帕特里夏）。同样，约翰、罗伯特、芭芭拉和琳达都是相互联系的。
您的任务实际上是形成图表并找到所有彼此不相交的连接子图。
虽然不是完整的算法，但我希望能帮助您入门。
You don't need to find the minimum spanning tree. That is really for finding the "best" edges in a graph that will still keep the graph connected. In other words, you don't care how John and Robert are connected, just that they are.
You say that the problem is that the graph would not be completely connected, but I think that is actually the point. If you represent graph edges by using the couples as you suggest, then the vertices that are connected form the groups that you are looking for.
In your example, James is connected to Mary and also James is connected to Patricia. No other person connects to any of those three vertices (if they did, you would have another couple that included them), which is why they form a single group of (James, Mary, Patricia). Similarly all of John, Robert, Barbara, and Linda are connected to each other.
Your task is really to form the graph and find all of the connected subgraphs that are disjoint from each other.
While not a full algorithm, I hope that helps get you started.
我认为你可以使用 dfs 和连接的组件轻松解决这个问题。因为每个人（节点）都与另一个人（边）有关系。因此，您有一个外循环，并对每个未访问的节点运行探索函数，并为探索函数探索的每个节点添加相同的数字。
例如
dfs() {整数组 0；
for(int i=0;i
if(nodes[i].visited==false){
探索（节点[i]，组）；
组++;
}
然后
你只需按组对节点进行排序就可以了。如果你想跟踪路径，你可以使用一个预编号来指示第一个、第二个节点被探索。等
（抱歉我的英语不好）！
I think that you can easily solve this with a dfs and connected components. Because every person(node) has a relation with an other one (edge). So you have an outer loop and run an explore function for every node which is unvisited and add the same number for every node explored by the explore function.
e.g
dfs() {int group 0;
for(int i=0;i<num_nodes;i++) {
if(nodes[i].visited==false){
explore(nodes[i],group);
group++;
}
}
then you simple have to sort the node by the group and then you are ready. if you want to track the path you can use a pre number which indicates which node was explored first, second..etc
(sorry for my bad english)!
名称集和名称对已经形成一个图表。具有节点和指向其他节点的指针的数据结构只是另一种表示形式，您不一定需要这种表示形式。 不相交集在我看来更容易实现，它们的目的正是为了跟踪同一性就像成对的事物连接在一起一样。
The sets of names and pairs of names already form a graph. A data structure with nodes and pointers to other nodes is just another representation, one that you don't necessarily need. Disjoint sets are easier to implement IMO, and their purpose in life is exactly to keep track of sameness as pairs of things are joined together.