题目大意：给出N个点，M条有向边，问是否任意两点u,v都满足u能到达v或者v能到达u
解题思路：强连通分量内的所有的点都满足，接着要判断一下其他的点能否满足了 求出所有的强连通分量，接着缩点，用桥连接，形成新的图(以下所说的点都是指新的图的点) 如果一个点同时指向另外两个不同的点，那么这两个点之间肯定是不能相互到达的，所以拓扑排序一下，就可以知道是否符合了
Edge{int from, to, next;}E[M];struct Node{int x, y;}node[M];int n, m, tot, dfs_clock, top, scc_cnt;int head[N], pre[N], stack[N], sccno[N], lowlink[N], in[N];void AddEdge(int u, int v) {E[tot].from = u;E[tot].to = v;E[tot].next = head[u];head[u] = tot++;}void init() {scanf(“%d%d”, &n, &m);memset(head, -1, sizeof(head));tot = 0;int u, v;for (int i = 0; i < m; i++) {scanf(“%d%d”, &node[i].x, &node[i].y);AddEdge(node[i].x, node[i].y);}}void dfs(int u) {pre[u] = lowlink[u] = ++dfs_clock;stack[++top] = u;int v;for (int i = head[u]; i != -1; i = E[i].next) {v = E[i].to;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++;while (1) {v = stack[top–];sccno[v] = scc_cnt;if (v == u) break;}}}int find() {int cnt = 0, num;for (int i = 1; i <= scc_cnt; i++) {if (in[i] == 0) {cnt++;num = i;}}if (cnt == 1)return num;return 0;}bool TopoOrder(){int cnt = 0;int u;while (u = find()) {in[u] = -1;for (int i = head[u]; i != -1; i = E[i].next) {in[E[i].to]–;}cnt++;}return cnt == scc_cnt;}void solve() {memset(pre, 0, sizeof(pre));memset(sccno, 0, sizeof(sccno));dfs_clock = top = scc_cnt = 0;for (int i = 1; i <= n; i++)if (!pre[i])dfs(i);if (scc_cnt == 1) {printf(“Yes\n”);return ;}memset(in, 0, sizeof(in));memset(head, -1, sizeof(head));tot = 0;int u, v;for (int i = 0; i < m; i++) {u = sccno[node[i].x];v = sccno[node[i].y];if (u != v) {in[v]++;AddEdge(u, v);}}int ans = 0;for (int i = 1; i <= scc_cnt; i++)if (in[i] == 0)ans++;if (ans > 1) {printf(“No\n”);return ;}if (TopoOrder())printf(“Yes\n”);elseprintf(“No\n”);}int main() {int test;scanf(“%d”, &test);while (test–) {init();solve();}return 0;}
，寂寞的人总是记住生命中出现的每一个人，
