問題:
http://acm.pku.edu.cn/JudgeOnline/problem?id=3256思路:
該題是一道簡單的DFS，結果卻歷經(jīng)了很多次RE，甚至還TLE，艾...
首先，對于paths可以用二維數(shù)組paths[MAX_N][MAX_N]來表示，雖然是很自然的事情，不過還是體現(xiàn)了選擇合適的數(shù)據(jù)結構對于解題的幫助
然后，對于每個起點(pasture in which each cow is grazing from beginning)依次深度優(yōu)先搜索，并計數(shù)
所有的搜索結束之后，清點計數(shù)，若某個pasture的計數(shù)等于cows的個數(shù)，那么就是符合條件的pasture
需要注意的一點是如何避免路徑中的環(huán)路，這里使用一維數(shù)組visited來標記經(jīng)過的pastures
代碼:
1 void
2 init()
3 {
4 int i, j, p;
5 memset(paths, 0, sizeof(paths));
6 memset(starts, 0, sizeof(starts));
7 memset(counts, 0, sizeof(counts));
8 scanf("%d %d %d", &k, &n, &m);
9 for(i=1; i<=k; i++)
10 scanf("%d", starts+i);
11 for(i=1; i<=m; i++) {
12 scanf("%d %d", &j, &p);
13 paths[j][p] = 1;
14 }
15 }
16
17 void
18 solve(int index)
19 {
20 int i;
21 visited[index] = 1;
22 ++counts[index];
23 for(i=1; i<=n; i++)
24 if(paths[index][i] && !visited[i]) {
25 solve(i);
26 }
27 }
28
29 void
30 output()
31 {
32 int i, total=0;
33 for(i=1; i<=n; i++)
34 if(counts[i] == k)
35 ++total;
36 printf("%d\n", total);
37 }