C++ 解法, 执行用时: 557ms, 内存消耗: 12920K, 提交时间: 2022-05-13 19:24:21

#include <bits/stdc++.h>
using namespace std;
inline void read(int &x)
{
    char c;int f=1;
    while(!isdigit(c=getchar()))if(c=='-')f=-1;
    x=(c&15);while(isdigit(c=getchar()))x=(x<<1)+(x<<3)+(c&15);
    x*=f;
}
inline void read(long long &x)
{
    char c;int f=1;
    while(!isdigit(c=getchar()))if(c=='-')f=-1;
    x=(c&15);while(isdigit(c=getchar()))x=(x<<1)+(x<<3)+(c&15);
    x*=f;
}
int t,n,m,i,j,dfn[100005],low[100005],col[100005],cnt,ti,stk[100005],tp,f[100005];
vector<int> v[100005];
bool flg;
void tarjan(int x)
{
	stk[++tp]=x;dfn[x]=low[x]=++ti;
	for(int u:v[x]){
		if(!dfn[u]) tarjan(u),low[x]=min(low[x],low[u]);
		else if(!col[u]) low[x]=min(low[x],dfn[u]);
	}
	if(low[x]==dfn[x]){
		cnt++;int sz=1;
		while(stk[tp]!=x) col[stk[tp--]]=cnt,sz++;
		col[stk[tp--]]=cnt;
        if(sz==2) flg=0;
	}
}
void solve()
{
    flg=1;
	read(n);read(m);for(i=1;i<=n;i++)dfn[i]=low[i]=col[i]=0,v[i].clear(),f[i]=0;cnt=ti=0;
	while(m--){int x,y;read(x);read(y);v[x].push_back(y);}
	for(i=1;i<=n;i++)if(!dfn[i])tarjan(i);
    if(!flg){puts("NO");return;}
	for(i=1;i<=n;i++)for(int u:v[i])if(col[u]==col[i]-1) f[col[i]]=1;
	for(i=2;i<=cnt;i++)if(!f[i]){
		puts("NO");return;
	}
	puts("YES");
}
int main()
{
	read(t);
	while(t--){
		solve();
	}
	return 0;
}