題意：給定無向圖，判斷是否任何兩點（x,y），可以從x到y(tǒng)或者從y到x.
The son can either go from x to y, or from y to x.
思路：Tarjan縮點后，充要條件是，成一條鏈。拓撲排序求判斷之。
#include<stdio.h>
#include<string.h>
#include<math.h>
#define maxn 1010
#define maxm 60600
struct edge{
int v;
int next;
}edges[maxm];
int last[maxn];
int edge_cnt;
void add_edge(int u,int v)
{
edges[edge_cnt].v = v;
edges[edge_cnt].next = last[u];
last[u] = edge_cnt++;
return ;
}
int dfn[maxn],low[maxn];
int color[maxn];
bool instack[maxn];
int st[maxn],top;
int cnt,scnt;
int n,m;
int N;
int mat[maxn][maxn];
int topo[maxn];
int dg[maxn];
int path[maxn];
int min(int x,int y)
{
return x<y?x:y;
}
void tarjan(int u)
{
dfn[u]=low[u]=cnt++;
st[++top]=u;
instack[u]=1;
for (int j=last[u];j!=-1;j=edges[j].next)
{
int v = edges[j].v;
if (dfn[v]==-1)
{
tarjan(v);
low[u]=min(low[u],low[v]);
}
else if (instack[v])
low[u]=min(low[u],low[v]);
}
if (low[u]==dfn[u])
{
scnt++;
int x;
do
{
x=st[top--];
instack[x]=0;
color[x]=scnt;
}while (x!=u);
}
return ;
}
void solve()
{
cnt = 0;
scnt = 0;
top = 0;
memset(dfn,-1,sizeof(dfn)); //初始這里居然錯了。
memset(instack,0,sizeof(instack));
for (int i=1;i<=n;i++)
if (dfn[i]==-1)
tarjan(i);
return ;
}
void init()
{
memset(last,-1,sizeof(last));
edge_cnt = 0;
scanf("%d%d",&n,&m);
for (int i=1;i<=m;i++)
{
int u,v;
scanf("%d%d",&u,&v);
add_edge(u,v);
}
return ;
}
void work()
{
solve();
N = scnt;//求出的強連通數(shù)
memset(mat,0,sizeof(mat));
for (int i=1;i<=n;i++)
{
for (int j=last[i];j!=-1;j=edges[j].next)
{
int v = edges[j].v;
mat[color[i]][color[v]]=1;
}
}
return ;
}
bool topsort()
{
memset(dg,0,sizeof(dg));
for (int i=1;i<=N;i++)
for (int j=1;j<=N;j++)
if (i!=j)//注意自己到自己不可。當是就在這里WA了！
dg[i] += mat[j][i];
for (int k=1;k<=N;k++)
{
int i=1;
while (dg[i]>0 && i<=n) i++;
if (i>n)
return 0;
dg[i]=-1;
for (int j=1;j<=N;j++)
dg[j]-=mat[i][j];
path[k]=i;
}
return 1;
}
int main()
{
int cas;
scanf("%d",&cas);
while (cas--)
{
init();
work();
bool flag = 1;
topsort();
for (int i=1;i<N;i++)
{
if (!mat[path[i]][path[i+1]])
{
flag = 0;
break;
}
}
if (flag)
puts("Yes");
else
puts("No");
}
return 0;
}
/*
3 3
1 2
2 3
3 1
8 11
1 2
2 3
2 5
2 6
3 5
4 3
5 2
5 4
6 7
6 8
7 6
*/