本文主要是介绍POJ 2762 Going from u to v or from v to u?(强联通，拓扑排序)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
http://poj.org/problem?id=2762
| Going from u to v or from v to u?
Description In order to make their sons brave, Jiajia and Wind take them to a big cave. The cave has n rooms, and one-way corridors connecting some rooms. Each time, Wind choose two rooms x and y, and ask one of their little sons go from one to the other. The son can either go from x to y, or from y to x. Wind promised that her tasks are all possible, but she actually doesn't know how to decide if a task is possible. To make her life easier, Jiajia decided to choose a cave in which every pair of rooms is a possible task. Given a cave, can you tell Jiajia whether Wind can randomly choose two rooms without worrying about anything? Input The first line contains a single integer T, the number of test cases. And followed T cases. The first line for each case contains two integers n, m(0 < n < 1001,m < 6000), the number of rooms and corridors in the cave. The next m lines each contains two integers u and v, indicating that there is a corridor connecting room u and room v directly. Output The output should contain T lines. Write 'Yes' if the cave has the property stated above, or 'No' otherwise. Sample Input 1 3 3 1 2 2 3 3 1 Sample Output Yes Source POJ Monthly--2006.02.26,zgl & twb |
题意：
给出一个有向图，判断对于任意两点u,v，是否可以从u到达v或者从v到达u。
分析：
判断有向图的单联通性。首先强联通缩点，得到一个DAG，如果这个DAG是一条单链，那么显然是可以的。如何判断DAG是否为单链呢？只要判断拓扑序是否唯一即可。
/*** Author : fcbruce <fcbruce8964@gmail.com>** Time : Tue 14 Oct 2014 11:37:19 AM CST**/
#include <cstdio>
#include <iostream>
#include <sstream>
#include <cstdlib>
#include <algorithm>
#include <ctime>
#include <cctype>
#include <cmath>
#include <string>
#include <cstring>
#include <stack>
#include <queue>
#include <list>
#include <vector>
#include <map>
#include <set>
#define sqr(x) ((x)*(x))
#define LL long long
#define itn int
#define INF 0x3f3f3f3f
#define PI 3.1415926535897932384626
#define eps 1e-10#ifdef _WIN32#define lld "%I64d"
#else#define lld "%lld"
#endif#define maxm 8964
#define maxn 1007using namespace std;int n,m;
int fir[maxn];
int u[maxm],v[maxm],nex[maxm];
int e_max;int pre[maxn],low[maxn],sccno[maxn];
int st[maxn],top;
int scc_cnt,dfs_clock;int deg[maxn];inline void add_edge(int _u,int _v)
{int e=e_max++;u[e]=_u;v[e]=_v;nex[e]=fir[u[e]];fir[u[e]]=e;
}void tarjan_dfs(int s)
{pre[s]=low[s]=++dfs_clock;st[++top]=s;for (int e=fir[s];~e;e=nex[e]){int t=v[e];if (pre[t]==0){tarjan_dfs(t);low[s]=min(low[s],low[t]);}else{if (sccno[t]==0)low[s]=min(low[s],pre[t]);}}if (low[s]==pre[s]){scc_cnt++;for (;;){int x=st[top--];sccno[x]=scc_cnt;if (x==s) break;}}
}void find_scc()
{scc_cnt=dfs_clock=0;top=-1;memset(sccno,0,sizeof sccno);memset(pre,0,sizeof pre);for (int i=1;i<=n;i++)if (pre[i]==0) tarjan_dfs(i);
}bool unique_toposort()
{top=-1;for (int i=1;i<=scc_cnt;i++){if (deg[i]==0) st[++top]=i;}for (int i=0;i<scc_cnt;i++){if (top==1 || top==-1) return false;int x=st[top--];for (int e=fir[x];~e;e=nex[e]){deg[v[e]]--;if (deg[v[e]]==0) st[++top]=v[e];}}return true;
}int main()
{
#ifdef FCBRUCEfreopen("/home/fcbruce/code/t","r",stdin);
#endif // FCBRUCEint T_T;scanf("%d",&T_T);while (T_T--){scanf("%d%d",&n,&m);e_max=0;memset(fir,-1,sizeof fir);for (int i=0,u,v;i<m;i++){scanf("%d%d",&u,&v);add_edge(u,v);}find_scc();int temp=e_max;e_max=0;memset(fir,-1,sizeof fir);memset(deg,0,sizeof deg);for (int e=0;e<temp;e++){if (sccno[u[e]]==sccno[v[e]]) continue;deg[sccno[v[e]]]++;add_edge(sccno[u[e]],sccno[v[e]]);}if (unique_toposort())puts("Yes");elseputs("No");}return 0;
}
这篇关于POJ 2762 Going from u to v or from v to u?(强联通，拓扑排序)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
