You are viewing a single comment's thread. Return to all comments →
public static List<int> componentsInGraph(List<List<int>> gb) { Dictionary<int, Node> map = new Dictionary<int, Node>(); Dictionary<int, bool> visited = new Dictionary<int, bool>(); foreach(List<int> edge in gb) { if(!map.ContainsKey(edge[0])) { map.Add(edge[0], new Node(edge[0])); visited.Add(edge[0], false); } if(!map.ContainsKey(edge[1])) { map.Add(edge[1], new Node(edge[1])); visited.Add(edge[1], false); } map[edge[0]].conn.Add(edge[1]); map[edge[1]].conn.Add(edge[0]); } int min = Int32.MaxValue; int max = Int32.MinValue; Queue<int> q = new Queue<int>(); foreach(int nodeKey in visited.Keys) { if(!visited[nodeKey]) { q.Enqueue(nodeKey); int nodeCount = 0; while(q.Count>0) { int key = q.Dequeue(); visited[key] = true; nodeCount++; foreach(int k in map[key].conn) { if(!visited[k]) { q.Enqueue(k); visited[k] = true; } } } min = Math.Min(min, nodeCount); max = Math.Max(max, nodeCount); } } return new List<int>(){min,max}; } public class Node { public int val; public HashSet<int> conn; public Node(int v) { val = v; conn = new HashSet<int>(); } }
Seems like cookies are disabled on this browser, please enable them to open this website
Components in a graph
You are viewing a single comment's thread. Return to all comments →
C#: