就是找强连通,然后判欧拉

#include<stdio.h>
#include<memory.h>

#define VMAX 1001
#define EMAX 6001
#define NULL 0

typedef struct Edge{
	int head,tail;
	Edge *hlink,*tlink;
}Edge;

typedef struct{
	Edge *firstin,*firstout;
	int ci,in,out;
	bool vis;
}Vex;

typedef struct{
	Vex V[VMAX];
	Edge E[EMAX];
	int vnum;
	int edgenum;
}Graph;

Graph G;
int cnum,order[VMAX],n,uset[VMAX];

void Init(){
	for(int i=1;i<=G.vnum;i++)
		uset[i]=i;
}

int Root(int pos){
	if(uset[pos]!=pos)
		uset[pos]=Root(uset[pos]);
	return uset[pos];
}

void Unite(int x,int y){
    uset[uset[x]]=uset[y];
}

void DFS(int pos){
	G.V[pos].vis=true;
	Edge *p=G.V[pos].firstout;
	while(p!=NULL){
		if(!G.V[p->tail].vis)
			DFS(p->tail);
		p=p->hlink;
	}
	order[n++]=pos;
}

void ReDFS(int pos,int cnum){
	G.V[pos].vis=true;
	G.V[pos].ci=cnum;
	Edge *p=G.V[pos].firstin;
	while(p!=NULL){
		if(!G.V[p->head].vis)
			ReDFS(p->head,cnum);
		p=p->tlink;
	}
}

void main()
{
	int t,i;
	scanf("%d",&t);
	while(t--){
		scanf("%d%d",&G.vnum,&G.edgenum);
		Init();
		n=0,cnum=0;
		bool flag=true;
		for(i=1;i<=G.vnum;i++){
			G.V[i].firstin=G.V[i].firstout=NULL;
			G.V[i].vis=false;
			G.V[i].in=G.V[i].out=0;
		}
		for(i=0;i<G.edgenum;i++){
			int x,y;
			scanf("%d%d",&x,&y);
			G.E[i].head=x;
			G.E[i].tail=y;
			G.E[i].hlink=G.V[x].firstout;
			G.E[i].tlink=G.V[y].firstin;
			G.V[y].firstin=G.V[x].firstout=&G.E[i];
			G.V[x].out++;
			G.V[y].in++;
		}
		memset(order,0,sizeof(order));
		for(i=1;i<=G.vnum;i++){
			if(!G.V[i].vis)
				DFS(i);
		}
		for(i=1;i<=G.vnum;i++)
			G.V[i].vis=false;
		for(i=n-1;i>=0;i--){
			if(!G.V[order[i]].vis){
				cnum++;
				ReDFS(order[i],cnum);
			}
		}
		if(cnum<=2){
			printf("Yes\n");
			continue;
		}
		int *_cin,*_cout;
		_cin=new int[n+1];
		_cout=new int[n+1];
		for(i=1;i<=n;i++)
			_cin[i]=_cout[i]=0;
		for(i=0;i<G.edgenum;i++){
			Edge *p=&G.E[i];
			if(G.V[p->head].ci!=G.V[p->tail].ci){
				_cout[G.V[p->head].ci]++;
				_cin[G.V[p->tail].ci]++;
			}
			Unite(p->head,p->tail);
		}
		int _root=Root(1);
		for(i=2;i<=G.vnum && flag;i++)
			if(Root(i)!=_root) 
				flag=false;
		int totalin=0,totalout=0;
		for(i=0;i<n && flag;i++){
			if(_cin[i]!=_cout[i]){
				if(_cin[i]==_cout[i]+1)
					totalout++;
				else if(_cin[i]==_cout[i]-1)
					totalin++;
				else flag=false;
			}
		}
		if(flag && ((totalin==0 && totalout==0) || (totalin==1 && totalout==1)))
			printf("Yes\n");
		else printf("No\n");
		delete[] _cin,_cout;
	}
}