Cycles Detection
Back to General discussions forum
In the notes, the problem definition states that the map will contain no roads connecting a city to itself (i.e. the graph has no loops). Is it safe to say that all maps have at least one path connecting any city to any other city (i.e. the graph is connected)?
Matthew, Hi!
You are right, the graph should be connected, otherwise I think the forumla will not work.
Problem statement says about it somewhat vaguely, perhaps: "...for any pair of cities there exists at least one way between them..." though I'm not sure how to rephrase this better...
Thanks! Finally solved this one.
Now that I look back at the problem statement, the way you have it worded is sufficient. I was just letting my imagination wander, as though Ruritania was an archipelago kingdom or something else crazy!
Any rate, this was one of the more challenging problems for me, I enjoyed it a lot. Good work!
I can't resist to show off my elegant program - http://www.codeabbey.com/index/task_solution?task=cycles-detection&user=vadim-tukaev&lang=Python
You said that my solution is very clever. That song named "Best girl in USSR". Somehow, I had the analogy between these two facts. Never mind, I have a particular sense of humor.
Don't worry about it. I found it amusing (catchy tune), but I was wondering what the link was between the two. May the best girl in the USSR can solve graph problems too? :)
Ok, I've tried three times already, with three different data sets and they all result to a wrong answer. I really think the checker is incorrect in this case. I will give only one example
11 G-T D-G O-G Q-D R-O Z-O V-T K-Z S-R P-Z T-V
I had Mathematica draw this graph, as any other, and this is NOT a cyclic graph. I even hand checked it. So why does the checker insist it is?
Here is my code. Any owner of a Raspberry Pi running Raspbian can test it
"11 G-T D-G O-G Q-D R-O Z-O V-T K-Z S-R P-Z T-V 6 P-T I-T G-I A-T K-A E-A 19 F-G M-G Z-M D-Z Y-F T-G I-Z B-M U-Y V-G K-V R-M J-V X-F A-U \ E-F H-A W-T O-X 22 N-D T-D V-N P-D M-P A-D B-V Z-T C-N L-B G-C Y-N R-Z Q-G K-Q \ X-A E-K H-Q W-X J-H S-J F-B 9 P-L M-P K-L A-L Y-A U-K H-K B-U V-A 20 U-J Z-U W-U T-J B-T P-Z O-U V-J Y-P C-U M-W X-V R-X D-Y I-Y \ N-X G-V F-P Q-C M-Z 15 K-R F-K D-R B-R P-B Z-D Q-B O-K M-Q W-F L-P E-R N-W S-Z E-K 15 E-S F-S I-E N-F Z-F U-F K-F M-N L-K V-I Y-Z W-K Q-K G-Q W-K 14 E-L U-E M-E D-U N-U S-N K-E T-L X-S P-K V-N Q-K A-L A-P 23 L-O D-O F-D S-D G-O K-F T-S C-O W-F Y-D Z-K Q-K E-W N-D H-T \ J-Z P-W X-Z M-Q V-T A-W I-E X-O 19 X-S V-S I-X H-S N-X C-X B-V Y-C U-Y K-U D-V L-V M-D R-N O-S \ E-R F-I P-B G-S 20 E-V F-V D-V U-E Y-D K-E I-E C-K W-Y T-C L-V M-L O-M H-E Q-H \ A-H P-K Z-Y J-U J-Q 14 G-H J-G P-H L-H Y-J O-P U-P C-O W-O Q-Y Z-Q N-L K-Q Y-P 11 E-F K-E G-F J-G O-E X-F W-O R-O V-K I-G O-X 21 R-E U-R Z-U H-Z M-R L-E J-R W-M F-M I-M N-Z B-I Q-I G-E S-E \ K-U Y-H P-B O-R A-K U-G 12 I-O B-O W-O A-B C-W H-O F-C M-W J-F T-I E-I R-M 17 I-Z H-I N-H K-H U-Z J-U O-J L-K P-J A-H C-A Q-O R-N E-Z V-I \ G-N G-N 14 H-Y X-H W-Y F-X K-F Q-W R-Q P-X V-F I-F N-H S-F L-I O-H 17 C-N Q-C Y-C Z-N V-N X-C A-V K-A R-A H-X I-R E-X P-A F-E S-H \ W-X M-Q 7 Y-Z A-Z T-Y V-Z O-T X-Z L-Z 20 F-T C-F X-C V-T H-T R-X I-H Y-I U-I A-H Z-H E-F B-X K-V M-T \ S-T Q-X W-Q O-W D-V 8 N-Z G-N L-Z Q-L F-Q H-Q V-G H-F 23 T-R Z-T V-T J-V H-T C-J K-R E-Z X-K P-H S-P A-P U-T O-R Y-P \ B-C N-C W-C I-J M-P D-H G-N B-T 9 W-I B-W D-B N-D A-D L-N P-L E-A Z-I 21 Y-V P-V F-Y E-V B-Y R-P J-F S-Y H-B W-F G-H U-Y L-S D-U N-W \ T-D I-P C-F Z-B O-L X-R 14 O-L R-L W-L Z-O V-R G-L F-Z J-W D-R X-W C-F Q-J T-W R-V 14 K-L D-K X-L P-X B-K R-B Z-P S-L A-R W-B Q-P G-P V-G O-D 8 H-S G-S E-S J-E Y-S B-E T-H J-S" // StringSplit[#, EndOfLine] & // StringCases[#, _ ~~ "-" ~~ ] & /@ # & // StringReplace[#, a ~~ _ ~~ b_ -> Rule[a, b]] & /@ # & // Map[First, #, {2}] & // {AcyclicGraphQ@ UndirectedGraph[#, VertexLabels -> All] // # /. {True -> 0, False -> 1} &, UndirectedGraph[#, VertexLabels -> All], #} & /@ # & // Grid
