BZOJ 1997[Hnoi2010]Planar

题面：

1997: [Hnoi2010]Planar

Time Limit: 10 Sec Memory Limit: 64 MB
Submit: 2046 Solved: 762
[Submit][Status][Discuss]

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 <iostream>
 2 #include <stdio.h>
 3 #include <string.h>
 4 #include <algorithm>
 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<u1||v1<u2)
34         return false;
35     return (v1<v2)==(u1<u2);
36 }
37 int find(int x)
38 {
39     if(x!=fa[x])
40         fa[x]=find(fa[x]);
41     return fa[x];
42 }
43 void UN(int x,int y)
44 {
45     int a=find(x),b=find(y);
46     if(a!=b)
47         fa[a]=b;
48 }
49 bool judge()
50 {
51     if(m>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 }

BZOJ 1997