How to group a list of connected pairs

Question

I have a list of connections from X to Y as follows:-

public class Connection
{
    private int X { get; set; }
    private int Y { get; set; }

    public Connection(int X, int Y)
    {
        this.X = X;
        this.Y = Y;
    }
}


List<Connection> connectionList = new List<Connection>();

connectionList.Add(new Connection(1, 2));
connectionList.Add(new Connection(1, 3));
connectionList.Add(new Connection(1, 4));
connectionList.Add(new Connection(2, 1));
connectionList.Add(new Connection(2, 3));
connectionList.Add(new Connection(2, 4));
connectionList.Add(new Connection(3, 1));
connectionList.Add(new Connection(3, 2));
connectionList.Add(new Connection(4, 1));
connectionList.Add(new Connection(4, 2));
connectionList.Add(new Connection(5, 6));

I want to now know from connectionList which groups I have. For example here are two connected graphs which represent the data above.

The desired output from the program would be two groups, A(1, 2, 3 4) and B(5, 6).

What is the best approach for this?

Answer 1

How about this;

var groups = new List<List<int>>();
foreach (var con in connectionList)
{
    if(!groups.Any(g => g.Contains(con.X) || g.Contains(con.Y)))
    {
        groups.Add(new List<int>() { con.X, con.Y }); //con.X is not part of any group, so we can create a new one with X and Y added, since both a are in the group       
    } 
    else 
    {
        var group = groups.First(g => g.Contains(con.X) || g.Contains(con.Y));
        if(!group.Contains(con.X)) group.Add(con.X);
        if(!group.Contains(con.Y)) group.Add(con.Y);
    }
}

Did this from the top of my head and didn't test it either. The purpose is simple;

• If nor X and Y exist in any group, add a new group.
• If either X or Y exists in a group, either Y or X should also be part of the group, thus add it.

Given your situation, this should give you two lists; one with (1,2,3,4) and one with (5,6).

EDIT: Click here to see the results.