题目链接
题目因为要根据上一次的输出结果来判断这次的输入, 也就是要求我们强制在线, 不能够把输入全部储存后处理
如果不要求强制在线, 我们可以先把所以输入储存起来, 从最后开始处理, 把删边改成加边, 如果在加边前不连通, 加边后连通, 也就等价意味着删边后会不连通, 再把输出储存起来, 最后从头到尾输出
既然强制在线, 我们可以换个思路
这里引进对偶图的概念:
对偶图是由平面图变来的, 平面图的概念就是: 图画在平面上, 边的交点只能为结点的图. 对偶图就是把边圈起来的一个个 "网格" 看作结点形成的图. 就网格图而言, 网格图里原来交叉点当作一个结点, 对偶图里就是把白块当作一个结点.
我们可以看出, 当把网格图的一条边删掉之后, 就等价于把边两边的白块联通了, 换句话说, 就是把对偶图里的两个结点联通了
有了以上前介知识后进一步分析, 删边后图不再联通就说明该边是唯一连接两点的路径了, 也就是说在对偶图中, 在加边前对偶图里的两个白块已经联通了
因为当删除一条边时发现这条边连接的两个空块已经联通了, 那么删除这条边后会出现一个空块连成的环, 于是就把里面的点和外面的点给隔开了.
如果还有不明白的可以看看这篇题解
转换成对偶图后就可以直接用并查集处理了
- #include <bits/stdc++.h>
- using namespace std;
- typedef long long ll;
- const double pi=acos(-1);
- const int mod=1<<30;
- const int maxn=2250000;
- int par[maxn];
- int rnk[maxn];
- bool flag=0;
- int n,k;
- void init(){
- for(int i=0;i<maxn;i++) par[i]=i,rnk[i]=0;
- }
- int find(int x){
- if(par[x]==x){
- return x;
- }
- else{
- return par[x]=find(par[x]);
- }
- //return par[x] == x ? x : (par[x] = find(par[x]));
- }
- void unite(int x,int y){
- x=find(x);y=find(y);
- if(x==y) return ;
- if(rnk[x]<rnk[y]){
- par[x]=y;
- }else {
- par[y]=x;
- if(rnk[x]==rnk[y]) rnk[x]++;
- }
- }
- bool same(int x,int y){
- return find(x)==find(y);
- }
- void solve(int a,int b,char c){
- //cout<<flag<<" ";
- // cout<<a<<""<<b<<" "<<c<<endl;
- int x,y;
- if(c=='N'){
- // cout<<233<<endl;
- if(a==1){
- x=0,y=b;
- }
- else if(a==n){
- x=0,y=(n-2)*(n-1)+b;
- }
- else{
- x=(a-2)*(n-1)+b,y=(a-1)*(n-1)+b;
- }
- }
- else if(c=='E'){
- // cout<<233<<endl;
- if(b==1){
- x=0,y=(a-1)*(n-1)+1;
- }
- else if(b==n){
- x=0,y=a*(n-1);
- }
- else {
- x=(a-1)*(n-1)+b-1,y=(a-1)*(n-1)+b;
- }
- }
- // cout<<x<<" "<<y<<endl;
- if(same(x,y)){
- cout<<"NIE\n";flag=1;
- return ;
- }
- cout<<"TAK\n";flag=0;
- unite(x,y);
- }
- int main(){
- init();
- scanf("%d%d",&n,&k);
- while(k--){
- int a1,a2,b1,b2,c1,c2;
- scanf("%d %d %c",&a1,&b1,&c1);
- getchar();
- scanf("%d %d %c",&a2,&b2,&c2);
- getchar();
- //cout<<par[2]<<" "<<par[0]<<endl;
- if(flag) solve(a2,b2,c2);
- else solve(a1,b1,c1);
- }
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2957548.html