// 强连通缩点 + 判断欧拉路( 用并查集判断连通性 ) + 输入加速外挂
// G++提交 63MS 无压力 ( 开外挂不要用C++提交 )
// C++提交 297-344MS 有点压力... ( 不开外挂 )

#include <stdio.h>
#include <string.h>
#include <queue>
#include <stack>
#include <algorithm>
#include <iostream>
using namespace std;
const int N=1001;

struct node {
  int a,b;
  int nxt;
}e[N*6];
int p[N];
int cnt;
int n,m;

int bin[N];
int find(int r) {
  if(r!=bin[r]) return bin[r]=find(bin[r]);
  return bin[r];
}
void merge(int x,int y) {
  x=find(x); y=find(y);
  bin[x]=y;
}

stack<int>s;
int DFN[N];
int low[N];
int belong[N];
bool instack[N];
int num,dep;
int in[N];
int out[N];
bool hash[N][N];

void tarjan(int u) {
  DFN[u]=low[u]=dep++;
  instack[u]=1;
  s.push(u);

  int i,v;
  for(i=p[u];i!=0;i=e[i].nxt) {
    v=e[i].b;
     if(DFN[v]==-1)
       tarjan(v) , low[u]=min(low[u],low[v]);
     else if(instack[v])
       low[u]=min(low[u],DFN[v]);
  }
  if(low[u]==DFN[u]) {
    num++;
     do {
        v=s.top(); s.pop();
        belong[v]=num;
        instack[v]=0;
     }while(v!=u);
  }
}

void init() {
  memset(DFN,-1,sizeof(DFN));
  memset(low,-1,sizeof(low));
  memset(instack,0,sizeof(instack));
  num=dep=0;

  memset(in,0,sizeof(in));
  memset(out,0,sizeof(out));

  memset(p,0,sizeof(p));
  cnt=0;
}
void addedge(int a,int b) {
  e[++cnt].b=b; e[cnt].nxt=p[a]; p[a]=cnt;
}

// 适用于 int (正数) , 输入外挂
inline void readint(int &ret) {
	char c;
	do {	c = getchar();
	} while(c < '0' || c > '9');
	ret = c - '0';
	while((c=getchar()) >= '0' && c <= '9')
		ret = ret * 10 + ( c - '0' );
}

int main()
{
  int t;
  int i,j;
  int a,b;
  scanf("%d",&t);
  while(t--) {

    // scanf("%d%d",&n,&m);
     readint(n); readint(m);

     init();

     for(i=1;i<=m;i++) {
       //scanf("%d%d",&a,&b);
        readint(a); readint(b);
        addedge(a,b);
     }

     for(i=1;i<=n;i++)
      if(DFN[i]==-1) tarjan(i);

     memset(hash,0,sizeof(hash));
     for(i=0;i<=n;i++) bin[i]=i;

// 在新建图中 记录 欧拉路的条件 in入度,out出度,merge()合并两个点
     for(i=1;i<=n;i++) {
        int u=belong[i];
        for(j=p[i];j!=0;j=e[j].nxt) {
           int v=belong[e[j].b];
           if(u!=v&&!hash[u][v]) {
              hash[u][v]=1;
              out[u]++; in[v]++;
              merge(u,v);
           }
        }
     }

// 判断是否是欧拉路
     int ru=0,chu=0,ct=0,mak=0;
     for(i=1;i<=num;i++) {
       if(bin[i]==i) ct++;
       if(in[i]==out[i]) continue;
       if(in[i]-out[i]==1) ru++;
       else if(out[i]-in[i]==1) chu++;
       else {mak=1; break;}
     }

     if(mak || ct!=1 || ru!=chu || ru>1 || chu>1 ) {
        puts("No");
     }
     else puts("Yes");

  }
}

• 错的。 (41) vsake 2014-05-26 12:54:39