題意是這樣:一個有向圖，問能否取任意兩個不同的節(jié)點(diǎn)u,v，u->v或者v->u存在路徑。
首先還是縮點(diǎn)，因?yàn)閺?qiáng)聯(lián)通分量里肯定任意兩點(diǎn)可達(dá)的。縮點(diǎn)后，圖變成DAG
下面就到了關(guān)鍵的部分了，什么情況下u、v互相不可達(dá)呢?顯然，u,v在兩條不同的鏈上。
然后就很簡單了，找最長鏈也可意，拓?fù)渑判蚺袛嘈蛄形ㄒ恍砸部梢浴Ｎ沂前春笳咦龅摹?br>
1 import java.io.*;
2 import java.util.Arrays;
3 import java.util.LinkedList;
4 public class Main {
5
6 /**
7 * @param args
8 */
9
10 static int g[]=new int[1001],ng[]=new int [1001],bid[]=new int[1001],stack[]=new int[1001],top;
11 static int v[]=new int[12005],nxt[]=new int[12005],c,n,m;
12 static int low[]=new int[1001],cnt,bc;
13 static int degree[]=new int[1001];
14 static LinkedList<Integer> q=new LinkedList<Integer>();
15 static void tarjan(int pos)
16 {
17 int nowid=cnt++;
18 low[pos]=nowid;
19 stack[++top]=pos;
20 for(int p=g[pos];p!=-1;p=nxt[p])
21 {
22 if(low[v[p]]==-1)
23 tarjan(v[p]);
24 low[pos]=Math.min(low[pos],low[v[p]]);
25 }
26 if(low[pos]>=nowid)
27 {
28 do
29 {
30 bid[stack[top]]=bc;
31 low[stack[top]]=Integer.MAX_VALUE;
32 }while(stack[top--]!=pos);
33 bc++;
34 }
35 }
36 static void dfs(int pos)
37 {
38 low[pos]=1;
39 stack[bid[pos]]=1;
40 for(int p=g[pos];p!=-1;p=nxt[p])
41 if(low[v[p]]==-1)
42 dfs(v[p]);
43 }
44 public static void main(String[] args) throws IOException{
45 StreamTokenizer in=new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
46 int testcase;
47 in.nextToken();
48 testcase=(int)in.nval;
49 while((testcase--)!=0)
50 {
51 int a,b;
52 in.nextToken();
53 n=(int)in.nval;
54 in.nextToken();
55 m=(int)in.nval;
56 Arrays.fill(g, -1);
57 c=0;
58 while((m--)!=0)
59 {
60 in.nextToken();
61 a=(int)in.nval;
62 in.nextToken();
63 b=(int)in.nval;
64 v[c]=b;
65 nxt[c]=g[a];
66 g[a]=c++;
67 }
68 Arrays.fill(low,-1);
69 Arrays.fill(bid,-1);
70 cnt=bc=0;
71 top=-1;
72 for(int i=1;i<=n;i++)
73 if(low[i]==-1)
74 tarjan(i);
75 Arrays.fill(ng,-1);
76 for(int i=1;i<=n;i++)
77 for(int p=g[i];p!=-1;p=nxt[p])
78 if(bid[v[p]]!=bid[i])
79 {
80 v[c]=bid[v[p]];
81 nxt[c]=ng[bid[i]];
82 ng[bid[i]]=c++;
83 }
84 q.clear();
85 Arrays.fill(degree,0);
86 for(int i=0;i<bc;i++)
87 for(int p=ng[i];p!=-1;p=nxt[p])
88 degree[v[p]]++;
89 for(int i=0;i<bc;i++)
90 if(degree[i]==0)
91 q.add(i);
92 int count=0;
93 while(!q.isEmpty()&&q.size()<=1)
94 {
95 int top=q.poll();
96 count++;
97 for(int p=ng[top];p!=-1;p=nxt[p])
98 if(true)
99 {
100 degree[v[p]]--;
101 if(degree[v[p]]==0)
102 q.add(v[p]);
103 }
104 }
105 if(q.isEmpty()&&count==bc)
106 System.out.println("Yes");
107 else
108 System.out.println("No");
109
110 }
111
112 }
113
114 }
115