Problem S. 13. (December 2005)

S. 13. Two players alternately move a piece on the vertices of a directed graph. One loses if he or she cannot move because the current vertex has no outward edge. If the piece is placed for the third time onto the same vertex, the game is a draw. Write a program that determines for each vertex the best possible result of the first player starting from that position.

The program will be run from the command line with two parameters containing the names of the input and output files. The input file contains the graph. The output file should contain whether any given vertex is a winning or a losing one.

The first line of the input file will contain the number of vertices and edges (n,m). The vertices are numbered from 1 to n. The next m lines will contain the origin and endpoint of each directed edge. The output file should have n lines, with the line containing W, D or L, depending on whether the first player starting from the vertex has a winning strategy, both players have a strategy to force a draw, or the second player has a winning strategy, respectively.

The graph can be assumed to have at most 1 000 000 vertices and at most 50 000 000 edges.

Example: the program is run with s13 graph.txt result.txt parameters.

The source code of the program (s13.pas, s13.cpp, ...) should be submitted.

(10 pont)

Deadline expired on January 16, 2006.

Statistics:

7 students sent a solution.
10 points:	Homolya Miklós, Nikházy László.
4 points:	2 students.
2 points:	2 students.
1 point:	1 student.

Problems in Information Technology of KöMaL, December 2005