题目链接：https://vjudge.net/contest/295959#problem/I 或者 http://poj.org/problem?id=2762
题意：输入多组样例,输入n个点和m条有向边,问该图中任意两点x, y之间是否满足x可以到y或者y可以到x。
一开始WA的原因是因为没注意到是或者, 如果是并且的话,就是一道简单的强连通分量的题,直接判断整个图是否为一个强连通分量
对于该题, 先用强连通分量进行缩点,简化图。图就变成了DAG,用拓扑排序判断图中点的入度, 图中入度为0的点只能存在一个, 若存在2个及以上的话,那么这2个点或多个点是无法互相到达。
在拓扑排序中用列队, 入度为0的点入队,每次都对列队中的数判断,若大于等于2则直接return 不满足。
#include<stdio.h>
#include<string.h>
#include<stack>
#include<queue>
#include<algorithm>
using namespace std; int n, m, cnt, cnt1;
int head[1010], head1[1010];
int dfn[1010], low[1010], vis[1010], deep, k_color, color[1010];
stack<int>S;
int in[1010], flag; struct Edge
{
int to, next;
}edge[6010], edge1[6010]; void add(int a, int b)
{
edge[++ cnt].to = b;
edge[cnt].next = head[a];
head[a] = cnt;
} void add1(int a, int b)
{
edge[++ cnt1].to = b;
edge[cnt1].next = head1[a];
head1[a] = cnt1;
} void tarjan(int now)
{
dfn[now] = low[now] = ++ deep;
vis[now] = 1;
S.push(now);
for(int i = head[now]; i != -1; i = edge[i].next)
{
int to = edge[i].to;
if(!dfn[to])
{
tarjan(to);
low[now] = min(low[now], low[to]);
}
else if(vis[to])
{
low[now] = min(low[now], dfn[to]);
}
}
if(dfn[now] == low[now])
{
k_color ++;
while(1)
{
int temp = S.top();
S.pop();
color[temp] = k_color;
vis[temp] = 0;
if(temp == now)
break;
}
}
} void topo_sort()
{
queue<int>Q;
while(!Q.empty())
Q.pop();
for(int i = 1; i <= k_color; i ++)
if(!in[i])
Q.push(i);
if(Q.size() > 1)
{
flag = 0;
return ;
}
while(!Q.empty())
{
int temp = Q.front();
Q.pop();
for(int i = head1[temp]; i != -1; i = edge[i].next)
{
int to = edge[i].to;
in[to] --;
if(!in[to])
Q.push(to);
if(Q.size() > 1)
{
flag = 0;
return ;
}
}
}
} int main()
{
int T;
scanf("%d", &T);
while(T --)
{
flag = 1;
cnt = deep = k_color = cnt1 = 0;
memset(head, -1, sizeof(head));
memset(in, 0, sizeof(in));
memset(head1, -1, sizeof(head1));
memset(dfn, 0, sizeof(dfn));
memset(low, 0, sizeof(low));
memset(vis, 0, sizeof(vis));
scanf("%d%d", &n, &m);
for(int i = 1; i <= m; i ++)
{
int a, b;
scanf("%d%d", &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 != -1; j = edge[j].next)
{
int to = edge[j].to;
int x = color[i], y = color[to];
if(x != y)
{
add1(x, y);
in[y] ++;
}
}
}
topo_sort();
if(flag)
printf("Yes\n");
else
printf("No\n");
}
return 0;
}