TREEISO - Tree Isomorphism
Given two undirected trees T1 and T2 with equal number of vertices N (1 ≤ N ≤ 100,000) numbered 1 to N, find out if they are isomorphic.
Two trees T1 and T2 are isomorphic if there is a bijection f between the vertex sets of T1 and T2 such that any two vertices u and v of T1 are adjacent in T1 if and only if f(u) and f(v) are adjacent in T2.
Input
The first line of input contains the number of test cases nTest (1<= nTest <= 400). Each test case contains:
- The first line contains the number of nodes N.
- Each of next N-1 lines contain two integers A, B, denoting that there is an edge in T1 between nodes A and B (1 ≤ A, B ≤ N).
- Each of next N-1 lines contain two integers A, B, denoting that there is an edge in T2 between nodes A and B (1 ≤ A, B ≤ N).
The sum of N over all test cases will not exceed 100,000.
Output
For each test case print YES if T1 and T2 are isomorphic and NO otherwise.
Example
Input: 2
4
4 2
4 1
2 3
4 2
2 3
4 1
5
3 4
3 2
3 5
3 1
3 4
4 2
2 5
2 1 Output: YES
NO
hide comments
nadstratosfer:
2019-07-08 06:48:45
Since the trees are undirected, aren't we simply supposed to check whether T1 and T2 are made of the same set of edges? Eg. can two trees be isomorphic if there's an edge between u and v in T1 but not in T2? |
|
jecht:
2017-08-31 01:52:38
Andrey, is the time limit really okay for Java? |
|
Medo:
2015-06-23 03:47:53
Medo: (edit) 2015-06-23 03:47:53
|
|
Carlo:
2015-04-15 18:25:34
I wrote Ahu Algorithm in O(NlogN) and it gets TLE, and I wrote the "naive" O(N^2) solution and gets accepted. wat? |
|
saadtaame:
2014-05-27 15:12:28
I'm getting SIGABRT at test 7, why is that happening? |
|
Andrey Naumenko:
2012-12-05 09:42:26
New tests added. |
|
van Helsing:
2012-11-05 04:14:16
Test cases are weak. |
|
:D:
2010-12-08 12:42:07
Mine was O(n*log(n)), but it was much faster in general case. I read on the forum, that there is a O(n) algo. Even for N=10000, N^2 would be too big. |
|
Ravi Kiran:
2010-11-24 13:15:07
What is the expected complexity for this problem?Will O(N^2) per case suffice? |
|
:D:
2010-11-22 19:37:44
I recall a graph isomorphism problem: TRANSL. Also a problem somewhat along the lines of isomorphism: PAIRGRPH. |
Added by: | indy256 |
Date: | 2010-11-10 |
Time limit: | 2s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: ASM64 |