Substitution Cipher

From Progteam

(Difference between revisions)
Jump to: navigation, search
Line 14: Line 14:
*If graph has a cycle, or is disconnected, you can't do it
*If graph has a cycle, or is disconnected, you can't do it
*Else, it's a connected DAG.
*Else, it's a connected DAG.
-
*Topological.
+
*Topological sort. Boom.
{{problem-stub}}
{{problem-stub}}
[[Sorting]]
[[Sorting]]

Revision as of 22:56, 16 June 2008


Substitution Cipher
Problem Number 1506
Sorter: hjfreyer
Source: Unknown
Link: http://acm.pku.edu.cn/JudgeOnline/problem?id=1506



Substitution Cipher is problem number 1506 on the Peking University ACM site.

Solution:

  • Turn the input into a list of "e<b" style rules.
  • Construct a graph from these rules.
  • If graph has a cycle, or is disconnected, you can't do it
  • Else, it's a connected DAG.
  • Topological sort. Boom.


Sorting
Personal tools