Jahid's blog

By Jahid, history, 9 years ago, In English

I Have tried this problem for long time but not getting accepted solution. My idea was: 1) Find Strongly Connected Components.

2) Form a DAG.

3) Run topsort on the DAG.

4) A DFS for number of assasin.

But I am getting continuously WA.

Problem:

Ezio needs to kill N targets located in N different cities. The cities are connected by some one way roads. As time is short, Ezio can send a massage along with the map to the assassin's bureau to send some assassins who will start visiting cities and killing the targets. An assassin can start from any city, he may visit any city multiple times even the cities that are already visited by other assassins. Now Ezio wants to find the minimum number of assassins needed to kill all the targets.

Input

Input starts with an integer T (≤ 70), denoting the number of test cases.

Each case starts with a blank line. Next line contains two integers N (1 ≤ N ≤ 1000) and M (0 ≤ M ≤ 10000), where N denotes the number of cities and M denotes the number of one way roads. Each of the next M lines contains two integers u v (1 ≤ u, v ≤ N, u ≠ v) meaning that there is a road from u to v. Assume that there can be at most one road from a city u to v.

Output

For each case, print the case number and the minimum number of assassins needed to kill all targets.

Sample Input:

3

5 4

1 2

1 3

4 1

5 1

7 0

8 8

1 2

2 3

3 4

4 1

1 6

6 7

7 8

8 6

Sample Output:

Case 1: 2

Case 2: 7

Case 3: 2

My Solution: http://paste.ubuntu.com/14006313/

Problem Link: http://www.lightoj.com/volume_showproblem.php?problem=1429

Thanks in Advance.

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by Jahid (previous revision, new revision, compare).

»
9 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Sorry, ignore this comment, I hadn't read that cities can be visited multiple times.

»
9 years ago, # |
  Vote: I like it +4 Vote: I do not like it

your step 1 and step 2 is correct. But i cannot find any logical reason that ,step 3 and step 4 will result in a minimum number of assassins. Google minimum path cover in DAG if you dont know about it. Then you can solve this problem. After your step 1 and 2, construct the graph in a way such that "minimum path cover in DAG" algorithm will work. Then solve that.