ofekpearl
BAN USERThis will not work for this example (prints out 3 instead of 2):
public static void main(String[] args) {
// TODO Auto-generated method stub
char[][] x = {
{'X','O','X'},
{'O','X','X'},
{'O','O','O'}
};
System.out.println(findisland(x));
}
private static int findisland(char[][] x) {
int count=0;
int[][] n = new int[x.length][x[0].length];
for (int i=0;i<x.length; i++) {
for(int j=0;j<x[i].length; j++) {
if(x[i][j]=='X') {
if(i>0 && n[i-1][j]>0) {
n[i][j] = n[i-1][j];
} else if(j>0 && n[i][j-1]>0){
n[i][j] = n[i][j-1];
} else {
n[i][j] = ++count;
}
}
}
}
return (count);
}
This solution will not work for this example:
public static void main(String[] args) {
// TODO Auto-generated method stub
char[][] x = {
{'X','O','X'},
{'O','X','X'},
{'O','O','O'}
};
System.out.println(findisland(x));
}
private static int findisland(char[][] x) {
int count=0;
int[][] n = new int[x.length][x[0].length];
for (int i=0;i<x.length; i++) {
for(int j=0;j<x[i].length; j++) {
if(x[i][j]=='X') {
if(i>0 && n[i-1][j]>0) {
n[i][j] = n[i-1][j];
} else if(j>0 && n[i][j-1]>0){
n[i][j] = n[i][j-1];
} else {
n[i][j] = ++count;
}
}
}
}
return (count);
}
You can create the DAG from the graph using DFS which is O(V+E):
1. compute DFS on the graph which gives a start and finish times for each node
2. Insert each finished vertex into the front of a linked list, going from the last finished to the first (backwards in the finishing times).
3. Return the linked list
I think this is simpler to understand (simple arrays instead of list of lists):
- ofekpearl May 11, 2019