Having Trouble Understanding why the Code Doesn't Work
Anonymous User
58
Really having difficulty understanding why this code does not work. I am trying to find the number of vertices in the largest connected component in an undirected graph. The input is given as a list of strings. Here, as in the friend circles problem, the relationship between vertices is transitive.
Example:
[[1,1,0],
[1,1,0],
[0,0,1]]
output: 2.
Example 2:
[[1,1,0],
[1,1,1],
[0,1,1]]
output: 3I really can't figure out why the following code doesn't work. Please help if you can figure it out.
class LargestConnectedComponent {
public static int findLargest(List<String> input) {
if (input == null) return 0;
LinkedList<Integer>[] adj = new LinkedList[input.size()];
int size = input.size();
//adj = new LinkedList[size];
for (int i = 0; i < size; i++) {
adj[i] = new LinkedList<>();
}
for (int i = 0; i < size; i++) {
for (int j = 0; j < input.get(i).length(); j++) {
if (input.get(i).charAt(j) == '1') {
if (i != j) {
adj[i].add(j);
}
}
}
}
boolean[] visited = new boolean[size];
int maxUsers = Integer.MIN_VALUE;
for (int i = 0; i < size; i++) {
if (!visited[i]) {
int counter = 1;
dfs(adj, visited, counter, i);
maxUsers = Math.max(maxUsers, counter);
}
}
return maxUsers;
}
private static void dfs(LinkedList<Integer>[] adj, boolean[] visited,
int counter, int i) {
if (visited[i]) {
return;
}
visited[i] = true;
counter += 1;
Iterator<Integer> iter = adj[i].listIterator();
while (iter.hasNext()) {
int newVertex = iter.next();
if (!visited[newVertex]) {
dfs(adj, visited, counter, newVertex);
}
}
}
}Comments (0)