msmajeed9
BAN USER/**
* Created by Majeed on 5/27/2014.
*/
public class BT {
public BTNode root;
// traverse reverse post-order and assign next to each
// same logic can be used for pre-order and in-order
// also this works for Binary and Binary Search both types of trees
public static BTNode postOrderSuccessor(BTNode root, BTNode next) {
if(root == null) return next;
root.next = next;
next = root;
next = postOrderSuccessor(root.right, next);
next = postOrderSuccessor(root.left, next);
return next;
}
// utility to print post order successor of each node by traversing it preorder
// fashion
public static void preorder(BTNode root) {
if(root == null) return;
System.out.print(root.data + ":");
if(root.next == null) System.out.print(null + " ");
else System.out.print(root.next.data + " ");
preorder(root.left);
preorder(root.right);
}
public static void main(String[] args) {
BT tree = new BT();
tree.root = new BTNode(1);
tree.root.left = new BTNode(2);
tree.root.right = new BTNode(3);
tree.root.left.left = new BTNode(4);
tree.root.left.right = new BTNode(5);
tree.root.right.left = new BTNode(6);
tree.root.right.right = new BTNode(7);
BT.postOrderSuccessor(tree.root, null);
BT.preorder(tree.root);
}
/*
* output : (node:post-order successor)
* 1:null 2:6 4:5 5:2 3:1 6:7 7:3
*/
}
import java.lang.reflect.Array;
import java.net.Inet4Address;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Scanner;
/**
* Created by Majeed on 5/27/2014.
*/
public class TriangleCounter {
private static int total;
private static boolean visited[];
public static int countTriangles(ArrayList[] g) {
int n = g.length;
visited = new boolean[n];
for(int i = 0; i < n; ++i) {
visited[i] = true;
dfs(i, i, 0, g);
}
return total / 6;
}
private static void dfs(int source, int v, int cnt, ArrayList[] g) {
++cnt;
for(int i = 0; i < g[v].size(); ++i) {
int to = (Integer) g[v].get(i);
if(!visited[to] && cnt < 3) {
visited[to] = true;
dfs(source, to, cnt, g);
}
else if(visited[to] && cnt == 3 && to == source) ++total;
}
visited[v] = false;
}
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
ArrayList g[];
int n = in.nextInt(), m = in.nextInt();
g = new ArrayList[n];
for(int i = 0; i < n; ++i) g[i] = new ArrayList();
for(int i = 0; i < m; ++i) {
int src = in.nextInt(), dest = in.nextInt();
g[src].add(dest); g[dest].add(src);
}
/*
for(int i = 0; i < n; ++i) {
for(int j = 0; j < g[i].size(); ++j)
System.out.print(g[i].get(j) + " ");
System.out.println();
}
*/
System.out.println(countTriangles(g));
}
}
Binary Exponentiation.
- msmajeed9 May 27, 2014