題目大意：
給出一個有向圖，這個圖，是否存在任意兩點a,b可達，這里的任意兩點a,b可達是說，只要從a能到b或者只要能從b到a就算是可達的。
解題思路：
poj是什么意思。先求出這個圖的強連通分量，然后縮點建圖，只要這個圖是一條鏈狀的，那么就可以滿足任意兩點都可達，否則不滿足。
原因是只要這個縮點建圖之后的圖是鏈狀的，那么必然從鏈的頭到尾，任意兩點都可達。一旦不是鏈狀，要么出現分叉，要么某個點入度>=2，這種情況在分叉的兩端都是無法可達的。所以只需要是鏈狀就可以了。這個可以用拓撲排序來做，也可以直接一遍dfs求出。
代碼：
#include <stack>
#include <vector>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;typedef struct node {int v, nxt;node(int a = 0, int b = 0) {v = a; nxt = b;}
}Edge;const int maxn = 1005;
const int maxm = 12010;int n, m;
stack<int> s;
Edge edge[maxm];
int ComponetNumber;
int tot, head[maxn];
int inComponet[maxn];
vector<int> vec[maxn];
int inx, inStack[maxn];
int low[maxn], dfn[maxn];
vector<int> Componet[maxn];
int in[maxn], out[maxn], vis[maxn];void init() {inx = tot = ComponetNumber = 0;while (!s.empty()) s.pop();memset(in, 0, sizeof(in));memset(dfn, 0, sizeof(dfn));memset(low, 0, sizeof(low));memset(out, 0, sizeof(out));memset(vis, 0, sizeof(vis));memset(head, -1, sizeof(head));memset(inStack, 0, sizeof(inStack));for (int i = 0; i < maxn; ++i) {vec[i].clear();Componet[i].clear();}
}
void add(int u, int v) {edge[tot] = Edge(v, head[u]);head[u] = tot++;
}
void tarjan(int x) {dfn[x] = low[x] = ++inx;inStack[x] = 2;s.push(x);for (int i = head[x]; ~i; i = edge[i].nxt) {int v = edge[i].v;if (!dfn[v]) {tarjan(v);low[x] = min(low[x], low[v]);} else if (inStack[v] == 2) {low[x] = min(low[x], dfn[v]);}}if (dfn[x] == low[x]) {++ComponetNumber;while(!s.empty()){int v = s.top(); s.pop();inStack[v] = 1;Componet[ComponetNumber].push_back(v);inComponet[v] = ComponetNumber;if (v == x) break;}}
}
void dfs(int p) {vis[p] = 1;int len = vec[p].size();for (int i = 0; i < len; ++i) {if (!vis[vec[p][i]]) dfs(vec[p][i]);}if (len > 1) vis[p] = 0;
}
int main() {ios::sync_with_stdio(false); cin.tie(0);int a, b, t; cin >> t;while (t--) {cin >> n >> m; init();for (int i = 0; i < m; ++i) {cin >> a >> b;add(a, b);}for (int i = 1; i <= n; ++i) {if (!dfn[i]) tarjan(i);}for (int i = 1; i <= n; ++i) {for (int j = head[i]; ~j; j = edge[j].nxt) {int v = edge[j].v;if (inComponet[i] != inComponet[v]) {++in[inComponet[v]];++out[inComponet[i]];vec[inComponet[i]].push_back(inComponet[v]);}}}for (int i = 1; i <= ComponetNumber; ++i) {if (!in[i]) { dfs(i); break; }}int flag = 1;for (int i = 1; i <= ComponetNumber; ++i) {if (!vis[i]) flag = 0;}if (flag) cout << "Yes\n";else cout << "No\n";}return 0;
}poj1741？
