# Substitution Cipher

### From Progteam

(Difference between revisions)

(created) |
|||

Line 3: | Line 3: | ||

|number=1506 | |number=1506 | ||

|difficulty | |difficulty | ||

- | | | + | |sorter=hjfreyer |

|source | |source | ||

}} | }} | ||

'''Substitution Cipher''' is problem number 1506 on the Peking University ACM | '''Substitution Cipher''' is problem number 1506 on the Peking University ACM | ||

- | site. | + | 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. | ||

{{problem-stub}} | {{problem-stub}} | ||

+ | [[Sorting]] |

## Revision as of 22:54, 16 June 2008

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.