Description Some major cities have subway systems in the form of a tree, i.e. between any pair of stations, there is one and only one way of going by subway. Moreover, most of these cities have a unique central station. Imagine you are a tourist in one of these cities and you want to explore all of the subway system. You start at the central station and pick a subway line at random and jump aboard the subway car. Every time you arrive at a station, you pick one of the subway lines you have not yet travelled on. If there is none left to explore at your current station, you take the subway line back on which you first came to the station, until you eventually have travelled along all of the lines twice,once for each direction. At that point you are back at the central station. Afterwards, all you remember of the order of your exploration is whether you went further away from the central station or back towards it at any given time, i.e. you could encode your tour as a binary string, where 0 encodes taking a subway line getting you one station further away from the central station, and 1 encodes getting you one station closer to the central station. Input On the first line of input is a single positive integer n, telling the number of test scenarios to follow.Each test scenario consists of two lines, each containing a string of the characters '0' and '1' of length at most 3000, both describing a correct exploration tour of a subway tree system. Output exploration tours of the same subway tree system, or the text "different" if the two strings cannot be exploration tours of the same subway tree system. Sample Input 2 0010011101001011 0100011011001011 0100101100100111 0011000111010101 Sample Output same different 其實題目意思就是求兩個有根樹是否同構，這個如果暴力法枚舉的話，復雜度是O(N^2)，一中經典的做法是哈希，思想就是使得不同結構的樹哈希值不同，而同構的樹哈希值相同。 我這個也是參考別人寫的，不同的是我先把01串轉換為了樹狀結構表示，然後再遞歸求哈希值，這樣好理解一點。 哈希的策略：先隨機產生一系列隨機數作為存到數組，接著從根節點出發，遞歸計算每個子樹的哈希值，將子樹的哈希值相加然後和父節點自己對應的數組上的隨機數相加得到父節點的哈希值。這個計算結果和子樹的順序是沒有關系的，所以同構的樹一哈希值一定是一樣的。對於異構的樹，必然在某些節點計算的哈希值不同，由於都是隨機產生的一些數字，所以他們相加值和另外一棵樹哈希值相同的概率也會非常低。（應該不能完全保證的，這裡我們加了個取模m的操作，根據鴿巢原理，當樹的數量超過m，必然有兩個樹的哈希值是會相同的，但這兩個樹卻未必是同構的，不知道大家覺得對不對？） [java] import java.util.*; public class SubwayTreeSstems1635 { static final int Hn=11000; static int h[]=new int[Hn]; static Random rand=new Random(System.currentTimeMillis()); static int m=1000000007; static int index=0; /** * @param args */ public static void main(String[] args) { run(); } private static void init() { for(int i=0;i<Hn;i++) h[i]=(rand.nextInt()%m); } public static void run() { Scanner in=new Scanner(System.in); int T=in.nextInt(); init(); for(int t=0;t<T;t++) { String s1=in.next(); Node tree1=createTree(s1); String s2=in.next(); Node tree2=createTree(s2); /*System.out.println(tree1.children.size()+" "+tree2.children.size()); displayTree(tree1); System.out.println(); displayTree(tree2);*/ int a=hash(tree1,1); int b=hash(tree2,1); //System.out.println(a+" "+b); if(a==b) { System.out.println("same"); } else { System.out.println("different"); } } } public static int hash(Node tree,int j) { int sum=h[j+5000];//j是樹的高度 for(Node n:tree.children) sum=(sum+h[j]*hash(n,j+1))%m;//把子樹的哈希值加到父節點上去 return (sum*sum)%m; } private static Node createTree(String s) { char[] seq=s.toCharArray(); Node root=new Node(0); Node p=root; int index=1; for(int i=0;i<seq.length;i++) { if(seq[i]=='0') { Node node =new Node(index++); connect(p,node); p=node; } else if(seq[i]=='1') { p=p.parent; } } //if(p==root) // System.out.println("create success!"); return root; } private static void connect(Node p, Node node) { node.parent=p; p.children.add(node); } public static void displayTree(Node tree) { System.out.println(tree); for(Node ch:tree.children) displayTree(ch); } } class Node { int id; Node parent=null; List<Node> children=new ArrayList<Node>(); public Node(int n) { id=n; } public String toString() { StringBuilder sb=new StringBuilder(); sb.append(id).append(": "); for(Node n:children) sb.append(n.id).append(" "); return sb.toString(); } }
