#Style I understand that this is a quick and dirty piece of code to earn some points on some code-challenge website. I will still offer some comments on style.

Style

I understand that this is a quick and dirty piece of code to earn some points on some code-challenge website. I will still offer some comments on style.

Create a VxV boolean matrix, edges where edges[v*V+w] is true if v and k are connected and false otherwise and V is the number of vertices in the graph. Note that this matrix is symmetric and you only ever need to compute the upper right half.

Note that you need to adjust your dfs() function so that you iterate over one row or column in the matrix depending on how you structure it.

(削除) Create a VxV boolean matrix, edges where edges[v*V+w] is true if v and k are connected and false otherwise and V is the number of vertices in the graph. Note that this matrix is symmetric and you only ever need to compute the upper right half. (削除ここまで)

(削除) Note that you need to adjust your dfs() function so that you iterate over one row or column in the matrix depending on how you structure it. (削除ここまで)

Now that the original question has been corrected from N < 106 to N < 10^6 this is no longer feasible.

Something like this (untested pseudo java-ish code):

private static void bfs(Graph g, int j){
 Queue<Node> fringe = new Queue<>();
 fringe.add(g.getNode(j));
 while(!fringe.isEmpty()){
 Node n = fringe.pop();
 n.mark();
 for(Node a : n.adjacent){
 if(!a.isVisited()){
 fringe.add(a);
 }
 }
 }
}

Edit: Fixed performance where a node could appear twice in the fringe

Something like this (untested pseudo java-ish code):

private static void bfs(Graph g, int j){
 Queue<Node> fringe = new Queue<>();
 Node start = g.getNode(j);
 start.mark();
 fringe.add(start);
 while(!fringe.isEmpty()){
 Node n = fringe.pop();
 for(Node a : n.adjacent){
 if(!a.isVisited()){
 a.mark();
 fringe.add(a);
 }
 }
 }
}