## Facebook Interview Question

SDE1s**Country:**United States

```
public static void main(String args[]) {
/**
* 0
* / \ 4
* / \ / \
* 3 \ / \
* \ 1----5
* \ /
* \ /
* 2
* /_\
*
* 7 cycles
*/
int[][] adjM = { { 0, 1, 0, 0, 0, 0}, { 0, 0, 1, 0, 1, 0}, { 0, 0, 1, 1, 0, 0}, { 1, 0, 0, 0 , 0, 0}, { 0, 0, 0, 0 , 0, 1}, { 0, 1, 0, 0 , 0, 0}};
int n = cyclesCount(adjM);
System.out.println(n);
}
public static int cyclesCount(int[][] adjm) {
int n = adjm.length;
int count = 0;
List<List<Integer>> nodesPath = new ArrayList<List<Integer>>();
for (int i = 0; i < n; i++) {
int[] conodes = adjm[i];
List<Integer> cnodes = new ArrayList<Integer>();
cnodes.add(i);
for (int j = 0; j < conodes.length; j++) {
if (adjm[i][j] == 1){
cnodes.add(j);
adjm[i][j] = -1;
count += cycles(adjm, i, j, 0, nodesPath, cnodes);
adjm[i][j] = 1;
}
}
}
return count;
}
public static int cycles(int[][] adjm, int snode, int cnode, int count, List<List<Integer>> nodesPath,
List<Integer> conodes) {
if (snode == cnode && !nodesPath.contains(conodes)) {
List<Integer> temp = new ArrayList<>(conodes);
nodesPath.add(temp);
return count + 1;
}
if (snode == cnode && nodesPath.contains(conodes))
return count;
int[] nodes = adjm[cnode];
int n = nodes.length;
for (int i = 0; i < n; i++) {
if (adjm[cnode][i] == 1) {
adjm[cnode][i] = -1;
if(i != snode)
conodes.add(i);
Collections.sort(conodes);
count = cycles(adjm, snode, i, count, nodesPath, conodes);
adjm[cnode][i] = 1;
if(i != snode)
conodes.remove(new Integer(i));
}
}
return count;
}
```

I guess its NP-Hard, www . cs . umd.edu/~jkatz/complexity/f11/lecture23.pdf

- sri December 14, 2017