Need help solving a problem using graphs in C

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 th开发者_C百科ey 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!

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.

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.