Luogu3209 HNOI2010 平面图判定 平面图、并查集

传送门

题意:$T$组数据,每组数据给出一个$N$个点,$M$条边,并存在一个$N$元环的图,试判断其是否为一个可平面图(如果存在一种画法,使得该图与给出的图同构且边除了在顶点处以外互相不相交,则称其为可平面图)$T \leq 100 , N \leq 200 , M \leq 10000$


关于平面图的性质可以参照这一个PPT

我们需要用到平面图的一个推论:在极大平面图(不能再加边的平面图)上,$M = 3 \times N - 6$(PPT里面有证明)

所以对于$M > 3 \times N - 6$的情况可以直接判定为NO,这样我们需要处理的问题的边数变为了$O(N)$级别。

接下来我们考虑$N$元环的作用。一个$N$元环将整个图分成了两个部分,一个在环内,一个在环外,而环内和环外连的边不能在非顶点处相交。这个问题可以通过并查集来实现,将一条边看做两个点(一个表示不与当前边排斥,一个表示与当前边排斥),对于互相排斥的边在并查集上合并,最后考虑是否存在一条边的两个点在一个集合内即可。

 #include<bits/stdc++.h>
 using namespace std;

 inline int read(){
     ;
     ;
     char c = getchar();
     while(!isdigit(c)){
         if(c == '-')
             f = ;
         c = getchar();
     }
     while(isdigit(c)){
         a = (a << ) + (a << ) + (c ^ ');
         c = getchar();
     }
     return f ? -a : a;
 }

 struct Edge{
     int start , end;
 }Ed[];
 map < int , int > lsh;
 ];

 bool cmp(Edge a , Edge b){
     return a.start < b.start;
 }

 inline void init(){
      ; i <= M <<  ; i++)
         fa[i] = i;
 }

 int find(int x){
     return fa[x] == x ? x : (fa[x] = find(fa[x]));
 }

 int main(){
 #ifdef LG
     freopen("3209.in" , "r" , stdin);
     freopen("3209.out" , "w" , stdout);
 #endif
     for(int T = read() ; T ; T--){
         N = read();
         M = read();
          ; i <= M ; i++){
             Ed[i].start = read();
             Ed[i].end = read();
         }
         lsh.clear();
          ; i <= N ; i++)
             lsh[read()] = i;
          * N - ){
             cout << "NO" << endl;
             continue;
         }
          ; i <= M ; i++){
             Ed[i].start = lsh[Ed[i].start];
             Ed[i].end = lsh[Ed[i].end];
             if(Ed[i].start > Ed[i].end)
                 swap(Ed[i].start , Ed[i].end);
         }
         init();
         sort(Ed +  , Ed + M +  , cmp);
         ;
          ; f && i <= M ; i++){
              ; f && j ; j--)
                 if(Ed[j].end > Ed[i].start && Ed[j].end < Ed[i].end && Ed[j].start < Ed[i].start){
                     fa[find(j)] = find(i + M);
                     fa[find(i)] = find(j + M);
                     if(find(i) == find(i + M) || find(j) == find(j + M))
                         f = ;
                 }
         }
         cout << (f ? "YES" : "NO") << endl;
     }
     ;
 }
上一篇:hihocoder 1066 无间道之并查集


下一篇:[hihoCoder]无间道之并查集