首页 > 代码库 > POJ 2762 Going from u to v or from v to u?(强联通，拓扑排序)
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 1007
using 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 FCBRUCE
freopen("/home/fcbruce/code/t","r",stdin);
#endif // FCBRUCE
int 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");
else
puts("No");
}
return 0;
}
POJ 2762 Going from u to v or from v to u?(强联通，拓扑排序)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。