Problem AE
Managing Packaging
Modern operating system distributions have tools to manage installed software, making it easy to keep the software up-to-date. Putting different pieces of software into ‘packages’ that can be installed separately keeps things simple and avoids duplicate effort and code. But this means that a package may depend on other packages, requiring their installation before that package can be installed. For example, many programs need to use ‘libc,’ which contains standard C-library functions. To keep track of these dependencies, many distributions use some sort of package manager.
When a user wants to install a new package (or set of packages), a package manager takes care of the headache of tracking down which packages are required to install the desired package. Of course, those may also depend on other packages.
For this problem, determine an order (if one exists) that allows a given list of packages to be installed. No package should be installed before all the packages it depends on are installed. You may assume that, at the beginning, no packages have been installed.
Input
Input consists of up to
Output
For each test case, output the order of package installation that allow them all to be installed after their respective dependencies. If there are multiple possible orderings, then give the ordering that is lexicographically first (using ASCII values for string ordering). If there is some group of packages that are not able to be ordered within the list, output ‘cannot be ordered’ instead of ordering the packages. Put a blank line between each pair of test cases.
Sample Input 1 | Sample Output 1 |
---|---|
14 libattr vim-X11 vim-common gtk2 libattr vim-common gtk2 libtiff atk pango glib2 libtiff zlib libjpeg atk pango xorg-x11-libs freetype glib2 glib2 zlib libjpeg xorg-x11-libs grep freetype grep pcre pcre freetype 3 emacs xorg-x11 lisp xorg-x11 lisp emacs 0 |
atk freetype glib2 libattr libjpeg pcre grep vim-common xorg-x11-libs pango zlib libtiff gtk2 vim-X11 cannot be ordered |
Sample Input 2 | Sample Output 2 |
---|---|
4 atk pango glib2 pango grep atk pango 0 |
pango atk glib2 grep |