tarjan求缩点，然后算缩点之后的图是不是一字链。
判断是不是一字链很简单，直接dfs求出一条最长边。
看最长边是不是等于缩点之后的数目即可。
#include <iostream>
#include<algorithm>
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<queue>
#include<stack>
#include<math.h>
using namespace std;
#define maxm 10000
#define maxn 1100
#define eps 0.000001
#define zero(x) ((fabs(x)<eps?0:x))
#define INF 99999999
struct gra
{struct list{int u,v,next;} edge[maxm];int head[maxn];int vis[maxn];int num;int n;int id[maxn];int od[maxn];int shuyu[maxn];int nums;int viss[maxn];int dnf[maxn],low[maxn],times,instack[maxn];stack<int>qq;void init(){memset(head,-1,sizeof(head));memset(vis,0,sizeof(vis));memset(shuyu,0,sizeof(shuyu));memset(dnf,0,sizeof(dnf));memset(low,0,sizeof(low));memset(instack,0,sizeof(instack));memset(viss,0,sizeof(viss));while(!qq.empty())qq.pop();num=0;nums=1;times=1;}void add(int u,int v){edge[num].u=u;edge[num].v=v;edge[num].next=head[u];head[u]=num++;}void tarjan(int x){dnf[x]=low[x]=times++;instack[x]=1;qq.push(x);for(int i=head[x]; i!=-1; i=edge[i].next){int y=edge[i].v;if(!dnf[y]){tarjan(y);low[x]=min(low[x],low[y]);}else if(instack[y]){low[x]=min(low[x],dnf[y]);}}if(low[x]==dnf[x]){int y=-1;while(x!=y){y=qq.top();shuyu[y]=nums;qq.pop();instack[y]=0;}nums++;}}void start(){for(int i=1; i<=n; i++){if(!dnf[i])tarjan(i);}}int dfs(int x,int p){int mm=p;for(int i=head[x]; i!=-1; i=edge[i].next){mm=max(mm,dfs(edge[i].v,p+1));}return mm;}
} G,g;
int main()
{int n,i,j,m,a,b,T;scanf("%d",&T);while(T--){scanf("%d%d",&n,&m);G.init();g.init();G.n=n;for(i=1; i<=m; i++){scanf("%d%d",&a,&b);G.add(a,b);}G.start();g.n=G.nums;int nin,nout;nin=nout=0;for(i=1; i<=G.n; i++){for(j=G.head[i]; j!=-1; j=G.edge[j].next){int u=G.edge[j].u;int v=G.edge[j].v;if(G.shuyu[u]==G.shuyu[v])continue;G.id[G.shuyu[v]]++;G.od[G.shuyu[u]]++;// cout<<G.shuyu[u]<<" - "<<G.shuyu[v]<<endl;g.add(G.shuyu[u],G.shuyu[v]);}}for(i=1; i<G.nums; i++){if(G.id[i]==0)nin++;if(G.od[i]==0)nout++;}if(nin>1||nout>1){cout<<"No"<<endl;continue;}for(i=1; i<G.nums; i++){if(G.id[i]==0)break;}// cout<<g.dfs(i,1)<<endl;if(g.dfs(i,1)==G.nums-1)cout<<"Yes"<<endl;else cout<<"No"<<endl;}return 0;
}