MWC '15 #4 P4: Dealing with Knots

View as PDF

Submit solution

All submissions

Best submissions

Points: 7

Time limit: 1.0s

Memory limit: 256M

Authors:

aurpine, Salarios77

Problem type

MathBunny123 needs string for his physics ISP. However, the string he has is a huge mess, it's stuck together and a lot of it is tangled (there are many different pieces). Luckily he has the legendary TangledStringAnalyzer9000. This revolutionary machine can scan the mess, assign each piece of string a number, and tell him which pairs of string are connected! MathBunny123 wants to check if string $A$ ~A~ is tangled with string $B$ ~B~; your job is to tell him if those two pieces of string are connected to each other by any means (if string $A$ ~A~ is connected to other pieces of string and one or many of those are connected to $B$ ~B~, then $A$ ~A~ is still tangled with string $B$ ~B~). His string is in such a mess that he managed to make the connections one way; they do not reciprocate.

Input Specification

The first line of input will contain the number of analyzed connections or number of pieces of string, $N$ ~N~ $(1 \le N \le 1000)$ ~(1 \le N \le 1000)~.

The next $N$ ~N~ lines of input will contain the connection in the form, a b, where $a$ ~a~ is the first string, $b$ ~b~ is the second string. $1 \le a,b \le 1000$ ~1 \le a,b \le 1000~.

The last line of input will be in the form, X Y, the pair of string pieces which will be checked to see if they are tangled or not. Each piece of string, $a$ ~a~, will only appear once as the first piece of string in a connection, a b.

Output Specification

Output Tangled if string $A$ ~A~ is connected to string $B$ ~B~, otherwise output Not Tangled.

Sample Input

Sample Output

Tangled

Comments

2

Ninjaclasher commented on Oct. 20, 2017, 2:57 p.m. ← edited →

Shouldn't $(1 \le a, b \le N)$ ~(1 \le a, b \le N)~ and not $(1 \le a, b \le 1000)$ ~(1 \le a, b \le 1000)~? Or am I not understanding the problem correctly?

Also:

Each piece of string, aa, will only appear once as the first piece of string in a connection, a b.

Doesn't sample case 1 violate this? Two connections start from 3.

4

injust commented on Oct. 20, 2017, 4:48 p.m.

The last line of input specifies the two pieces of string to be checked

1

Daniel123 commented on April 17, 2016, 7:45 p.m. ← edit 4 →

5 1 2 2 3 3 4 4 5 5 3 1 5

4

r3mark commented on April 17, 2016, 8:01 p.m.

Tangled