http://poj.org/problem?id=2762
题意：
给出有向图，判断任意两个点u和v，是否可以从u到v或者从v到u。
思路：
判断图是否是单连通的。
首先来一遍强连通缩点，重新建立新图，接下来我们在新图中找入度为0的点，入度为0的点只能有1个，如果有多个那么这些个点肯定是不能相互到达的。
如果只有一个入度为0的点，走一遍dfs判断新图是否是单链，如果有分支，那么分支上的点肯定是不能相互到达的。
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<vector>
#include<stack>
#include<queue>
#include<cmath>
#include<map>
using namespace std;
typedef long long LL; const int maxn=+; int n,m; int x[maxn],y[maxn];
int in[maxn];
int flag; vector<int> G[maxn];
vector<int> new_G[maxn]; stack<int> S;
int pre[maxn],lowlink[maxn],sccno[maxn],dfs_clock,scc_cnt; void dfs(int u)
{
pre[u] = lowlink[u] = ++dfs_clock;
S.push(u);
for (int i = ; i < G[u].size(); i++)
{
int v = G[u][i];
if (!pre[v])
{
dfs(v);
lowlink[u] = min(lowlink[u], lowlink[v]);
}
else if(!sccno[v])
lowlink[u] = min(lowlink[u], pre[v]);
}
if (pre[u] == lowlink[u])
{
scc_cnt++;
for(;;)
{
int x = S.top(); S.pop();
sccno[x] = scc_cnt;
if (x == u) break;
}
}
} void find_scc(int n)
{
dfs_clock = scc_cnt = ;
memset(pre, , sizeof(pre));
memset(sccno, , sizeof(sccno));
for (int i = ; i <= n; i++)
if (!pre[i]) dfs(i);
} void dfs2(int u)
{
if(flag==) return;
if(new_G[u].size()>) {flag=;return;}
if(new_G[u].size()!=) dfs2(new_G[u][]);
} void rebulid()
{
for(int i=;i<=scc_cnt;i++) {new_G[i].clear();in[i]=;}
for(int i=;i<m;i++)
{
if(sccno[x[i]]!=sccno[y[i]])
{
new_G[sccno[x[i]]].push_back(sccno[y[i]]);
in[sccno[y[i]]]=;
}
}
int num=;
int pos;
for(int i=;i<=scc_cnt;i++)
{
if(in[i]==) {num++;pos=i;}
if(num>=) {flag=;return;}
}
if(flag) dfs2(pos);
} int main()
{
//freopen("D:\\input.txt","r",stdin);
int T;
scanf("%d",&T);
while(T--)
{
flag=;
scanf("%d%d",&n,&m);
for(int i=;i<=n;i++) G[i].clear();
for(int i=;i<m;i++)
{
scanf("%d%d",&x[i],&y[i]);
G[x[i]].push_back(y[i]);
}
find_scc(n);
rebulid();
if(flag) puts("Yes");
else puts("No");
}
return ;
}