题面：

1997: [Hnoi2010]Planar

Time Limit: 10 Sec  Memory Limit: 64 MB

Submit: 2046  Solved: 762

[][][]

Description

Input

Output

Sample Input

2

6 9

1 4

1 5

1 6

2 4

2 5

2 6

3 4

3 5

3 6

1 4 2 5 3 6

5 5

1 2

2 3

3 4

4 5

5 1

1 2 3 4 5

Sample Output

NO

YES

HINT

 

两条边若在回路内相交,在回路外也会相交,所以两条相交的边只能一条在回路内,一条在回路外。

用并查集维护,判断两条边的情况是否矛盾。

1 #include 
      
        2 #include 
       
         3 #include 
        
          4 #include 
         
           5 using namespace std; 6 #define maxn 10001 7 int u[maxn],v[maxn]; 8 int T,n,m; 9 int rk[maxn],fa[maxn];10 inline int read()11 {12     int s=0,f=1;13     char ch=getchar();14     while(ch<'0'||ch>'9')15     {16         if(ch=='-')f=-1;17         ch=getchar();18     }19     while(ch>='0'&&ch<='9')20         s=(s<<1)+(s<<3)+ch-'0',ch=getchar();21     return s*f;22 }23 bool cross(int u1,int v1,int u2,int v2)24 {25     if(u1==u2||u1==v2||v1==u2||v1==v2)26         return false;27     u1=rk[u1],v1=rk[v1];28     u2=rk[u2],v2=rk[v2];29     if(u1>v1)30         swap(u1,v1);31     if(u2>v2)32         swap(u2,v2);33     if(v2
          
           
            n*3-6)52 return false;53 int i,j,x,y;54 for(i=1;i<=(m<<1);i++)55 fa[i]=i;56 for(i=1;i<=m;i++)57 for(j=i+1;j<=m;j++)58 {59 if(cross(u[i],v[i],u[j],v[j]))60 {61 x=find(i),y=find(j);62 if(x==y)63 return false;64 UN(x,j+m);65 UN(y,i+m);66 }67 }68 return true;69 }70 int main()71 {72 T=read();73 while(T--)74 {75 n=read();76 m=read();77 int i;78 for(i=1;i<=m;i++)79 {80 u[i]=read();81 v[i]=read();82 }83 for(i=1;i<=n;i++)84 rk[read()]=i;85 puts(judge()?"YES":"NO");86 }87 88 }