C++ 解法, 执行用时: 19ms, 内存消耗: 828K, 提交时间: 2021-10-15 22:43:11

#include<bits/stdc++.h>
using namespace std;
struct Node
{
  int next,to;
}edge[100001];
struct Edge
{
  int u,v;
}e[20001];
int head[1001],num,n,m,id[1001],cnt;
int vis[1001];
void add(int u,int v)
{
  num++;
  edge[num].next=head[u];
  head[u]=num;
  edge[num].to=v;
}
bool dfs(int x,int pa,int k)
{int i;
  vis[x]=k^1;
  for (i=head[x];i;i=edge[i].next)
    {
      int v=edge[i].to;
      if (vis[v]==-1)
    {
      if (!dfs(v,x,k^1)) return 0;
    }
      else
    {
      if (vis[v]==(k^1))
        return 0;
    }
    }
  return 1;
}
int main()
{int T,i,j,x;
  cin>>T;
  while (T--)
    {
      cin>>n>>m;
      for (i=1;i<=m;i++)
    {
      scanf("%d%d",&e[i].u,&e[i].v);
    }
      memset(id,0,sizeof(id));
      for (i=1;i<=n;i++)
    {
      scanf("%d",&x);
      id[x]=i;
    }
      if (m>3*n-6)
    {
      printf("NO\n");
      continue;
    }
      num=0;
      memset(head,0,sizeof(head));
      for (i=1;i<=m;i++)
    {
      int u=e[i].u,v=e[i].v;
      if (id[u]>id[v]) swap(u,v);
      for (j=1;j<i;j++)
        {
          int p=e[j].u,q=e[j].v;
          if (id[p]>id[q]) swap(p,q);
          if (id[u]<id[p]&&id[v]<id[q]&&id[p]<id[v]) add(i,j),add(j,i);
          if (id[p]<id[u]&&id[q]<id[v]&&id[u]<id[q]) add(i,j),add(j,i);
        }
    }
      memset(vis,-1,sizeof(vis));
      for (i=1;i<=m;i++)
    if (vis[i]==-1)
    {
      if (!dfs(i,0,0)) break;
    }
      if (i>m) printf("YES\n");
      else printf("NO\n");
    }
     return 0;
}

C++(g++ 7.5.0) 解法, 执行用时: 22ms, 内存消耗: 792K, 提交时间: 2022-08-22 11:24:19

#include<bits/stdc++.h>
using namespace std;
struct Node
{
  int next,to;
}edge[100001];
struct Edge
{
  int u,v;
}e[20001];
int head[1001],num,n,m,id[1001],cnt;
int vis[1001];
void add(int u,int v)
{
  num++;
  edge[num].next=head[u];
  head[u]=num;
  edge[num].to=v;
}
bool dfs(int x,int pa,int k)
{int i;
  vis[x]=k^1;
  for (i=head[x];i;i=edge[i].next)
    {
      int v=edge[i].to;
      if (vis[v]==-1)
    {
      if (!dfs(v,x,k^1)) return 0;
    }
      else
    {
      if (vis[v]==(k^1))
        return 0;
    }
    }
  return 1;
}
int main()
{int T,i,j,x;
  cin>>T;
  while (T--)
    {
      cin>>n>>m;
      for (i=1;i<=m;i++)
    {
      scanf("%d%d",&e[i].u,&e[i].v);
    }
      memset(id,0,sizeof(id));
      for (i=1;i<=n;i++)
    {
      scanf("%d",&x);
      id[x]=i;
    }
      if (m>3*n-6)
    {
      printf("NO\n");
      continue;
    }
      num=0;
      memset(head,0,sizeof(head));
      for (i=1;i<=m;i++)
    {
      int u=e[i].u,v=e[i].v;
      if (id[u]>id[v]) swap(u,v);
      for (j=1;j<i;j++)
        {
          int p=e[j].u,q=e[j].v;
          if (id[p]>id[q]) swap(p,q);
          if (id[u]<id[p]&&id[v]<id[q]&&id[p]<id[v]) add(i,j),add(j,i);
          if (id[p]<id[u]&&id[q]<id[v]&&id[u]<id[q]) add(i,j),add(j,i);
        }
    }
      memset(vis,-1,sizeof(vis));
      for (i=1;i<=m;i++)
    if (vis[i]==-1)
    {
      if (!dfs(i,0,0)) break;
    }
      if (i>m) printf("YES\n");
      else printf("NO\n");
    }
}