第9类商标有网站开发,软件设计包括哪些内容,html网站建设实例代码,vs210做网站正题
题目链接:https://darkbzoj.tk/problem/4423 题目大意
给出一个n∗nn*nn∗n的网格图#xff0c;然后四联通的点之间连接。每次删掉一条边求这条边的两个点是否连通。强制在线。 1≤n≤1500,1≤m≤2n(n−1)1\leq n\leq 1500,1\leq m\leq 2n(n-1)1≤n≤1500,1≤m≤2n(n−…正题
题目链接:https://darkbzoj.tk/problem/4423 题目大意
给出一个n∗nn*nn∗n的网格图然后四联通的点之间连接。每次删掉一条边求这条边的两个点是否连通。强制在线。
1≤n≤1500,1≤m≤2n(n−1)1\leq n\leq 1500,1\leq m\leq 2n(n-1)1≤n≤1500,1≤m≤2n(n−1) 解题思路
转换成对偶图之后就可以变成加边判断连通性的问题了。
一个很简单的理解就是如果新的删去的边在对偶图构成了一个环那么就会被分成环内和环外了。
时间复杂度O(mα(m))O(m\alpha(m))O(mα(m)) code
#includecstdio
#includecstring
#includealgorithm
using namespace std;
const int N1600;
int n,k,fa[N*N];
int find(int x)
{return (fa[x]x)?(x):(fa[x]find(fa[x]));}
void Unionm(int x,int y){xfind(x);yfind(y);if(xy)return;fa[x]y;
}
int main()
{scanf(%d%d,n,k);bool last1;for(int i1;i(n1)*(n1);i)fa[i]i;for(int i1;in;i){Unionm(i,i1);Unionm((i-1)*(n1)1,i*(n1)1);Unionm(n*(n1)i,n*(n1)i1);Unionm((i-1)*(n1)n1,i*(n1)n1);}for(int i1;ik;i){int x1,x2,y1,y2,x,y,p,q;char op1[2],op2[2],op;scanf(%d%d%s,x1,y1,op1);scanf(%d%d%s,x2,y2,op2);if(last)xx1,yy1,opop1[0];else xx2,yy2,opop2[0];if(opN){px*(n1)y1;q(x-1)*(n1)y1;pfind(p);qfind(q);if(p!q)last1,puts(TAK);else last0,puts(NIE);}else{px*(n1)y1;qx*(n1)y;pfind(p);qfind(q);if(p!q)last1,puts(TAK);else last0,puts(NIE);}Unionm(p,q);}return 0;
}
