对偶图并查集 BZOJ4423

题目链接

题目因为要根据上一次的输出结果来判断这次的输入，也就是要求我们强制在线，不能够把输入全部储存后处理

如果不要求强制在线，我们可以先把所以输入储存起来，从最后开始处理，把删边改成加边，如果在加边前不连通，加边后连通，也就等价意味着删边后会不连通，再把输出储存起来，最后从头到尾输出

既然强制在线，我们可以换个思路

这里引进对偶图的概念:

对偶图是由平面图变来的，平面图的概念就是：图画在平面上，边的交点只能为结点的图。对偶图就是把边圈起来的一个个“网格”看作结点形成的图。就网格图而言，网格图里原来交叉点当作一个结点，对偶图里就是把白块当作一个结点。

我们可以看出，当把网格图的一条边删掉之后，就等价于把边两边的白块联通了，换句话说，就是把对偶图里的两个结点联通了

有了以上前介知识后进一步分析，删边后图不再联通就说明该边是唯一连接两点的路径了，也就是说在对偶图中，在加边前对偶图里的两个白块已经联通了

因为当删除一条边时发现这条边连接的两个空块已经联通了，那么删除这条边后会出现一个空块连成的环，于是就把里面的点和外面的点给隔开了。

如果还有不明白的可以看看这篇题解

转换成对偶图后就可以直接用并查集处理了

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 typedef long long ll;
 4 const double pi=acos(-1);
 5 const int mod=1<<30;
 6 const int maxn=2250000;
 7 int par[maxn];
 8 int rnk[maxn];
 9 bool flag=0;
10     int n,k;
11 void init(){
12     for(int i=0;i<maxn;i++) par[i]=i,rnk[i]=0;    
13 }
14 int find(int x){
15     if(par[x]==x){
16         return x;
17     }
18     else{
19         return par[x]=find(par[x]);
20     }
21     //return par[x] == x ? x : (par[x] = find(par[x]));
22 }
23 void unite(int x,int y){
24     x=find(x);y=find(y);
25     if(x==y) return ;
26     if(rnk[x]<rnk[y]){
27         par[x]=y;
28     }else {
29         par[y]=x;
30         if(rnk[x]==rnk[y]) rnk[x]++;
31     }
32 }
33 bool same(int x,int y){
34     return find(x)==find(y);
35 }
36 void solve(int a,int b,char c){
37     //cout<<flag<<" ";
38 //    cout<<a<<" "<<b<<" "<<c<<endl;
39     int x,y;
40     if(c=='N'){
41     //    cout<<233<<endl;
42         if(a==1){
43             x=0,y=b;
44         }
45         else if(a==n){
46             x=0,y=(n-2)*(n-1)+b;
47         }
48         else{
49             x=(a-2)*(n-1)+b,y=(a-1)*(n-1)+b;
50         }
51     }
52     else if(c=='E'){
53     //    cout<<233<<endl;
54         if(b==1){
55             x=0,y=(a-1)*(n-1)+1;
56         }
57         else if(b==n){
58             x=0,y=a*(n-1);
59         }
60         else {
61             x=(a-1)*(n-1)+b-1,y=(a-1)*(n-1)+b;
62         }
63     }    
64 //    cout<<x<<" "<<y<<endl;
65     if(same(x,y)){
66         cout<<"NIE
";flag=1;
67         return ;
68     }
69     cout<<"TAK
";flag=0;
70     unite(x,y);    
71 }
72 int main(){
73     init();
74     scanf("%d%d",&n,&k);
75     while(k--){
76         int a1,a2,b1,b2,c1,c2;
77         scanf("%d %d %c",&a1,&b1,&c1);
78         getchar();
79         scanf("%d %d %c",&a2,&b2,&c2);
80         getchar();
81         //cout<<par[2]<<" "<<par[0]<<endl;
82         if(flag) solve(a2,b2,c2);
83         else solve(a1,b1,c1);
84     }
85     return 0;
86 }

对偶图 并查集 BZOJ4423

对偶图并查集 BZOJ4423