[HNOI2010] 平面图判定 planar

标签：二分图判定。
题解：

　　首先可以把题目中给你的那个环给画出来，这样就可以发现对于任意一个图来说，如果两条边要相交，就不能让他们相交，那么这两条边就要一条在里面一条在外面，如果把环画成一条链，那么就是一条在下面，一条在上面。于是我们想到对于边，O(n2)的枚举，判断是否相交即可，如果相交的话，就要连一条边，到时候判断这一个图（把原图边看成新图的点）是不是二分图即可，简单的二分图染色判定即可。
　　当然了O(n2)对于10000条边来说，因为有多组数据，会被卡掉，那么我们就要想办法，点这么少，边这么多，那么最多能有多少条边而且这个图是平面图呢？通过手玩找规律，先画出一条环，有n条边，然后这个环的一个点向非相邻的n-3个点连接n-3条边可以保证两两不相交，外面一侧如此，故如果边数m>n*3-6，就直接判断NO即可。保证了复杂度。

#include<queue>

#include<cstdio>

#include<cstring>

#include<iostream>

#include<algorithm>

using namespace std;

const int MAXN=,MAXM=;

int Case,n,m;

int F[],T[],rk[MAXN],con[MAXM][MAXM],color[MAXM];

inline int gi(){int res; scanf("%d",&res); return res;}

bool judge(int S)

{

  queue<int>Q;

  color[S]=;

  Q.push(S);

  while(!Q.empty())

    {

      int u=Q.front();

      Q.pop();

      for(int i=;i<=m;i++)

        if(con[u][i])

          {

            if(color[i]==-)

              {

                color[i]=!color[u];

                Q.push(i);

              }

            else if(color[i]==color[u])

              return ;

          }

    }

  return ;

}

int main()

{

  Case=gi();

  while(Case--)

    {

      n=gi(); m=gi();

      for(int i=;i<=m;i++)

        {

          F[i]=gi();

          T[i]=gi();

        }

      for(int i=;i<=n;i++) rk[gi()]=i;

      if(m>n*-){puts("NO");continue;}

      memset(con,,sizeof con);

      memset(color,-,sizeof color);

      for(int i=,A,B,C,D;i<m;i++)

        for(int j=i+;j<=m;j++)

          {

            A=rk[F[i]],B=rk[T[i]];

            C=rk[F[j]],D=rk[T[j]];

            if(A>B)swap(A,B);

            if(C>D)swap(C,D);

            if((B>C && B<D && C>A) || (D>A && D<B && A>C))

                con[i][j]=con[j][i]=;

          }

      bool flag=;

      for(int i=;i<=m;i++)

        if(color[i]==- && !judge(i))

          { flag=; break; }

      if(flag)puts("NO");

      else puts("YES");

    }

  return ;

}