bc #77 ||hdu 5652 India and China Origins (图的动态连通性问题，并查集or 二分+bfs验证连通性)
题目链接 题意：没图不好描述，有中文题面中文题面，直接看吧。 思路：据说这道题有三种做法。 当时比赛一种都不会。
先说一种：做法是把格子看成点，可以到达的相邻格子之间看成有边相连，然后倒过来用并查集判断无向图的连通性。具体做法是：先统计初始所有空的位置，然后把所有要增加的山都加上（先统计空的位置是因为山之后要去掉，而去掉以后要得到该点的标号），然后将把所有空的点以及china(设标号为n*m+1)点,和india(**设标号为n*m+2) **点通过并查集来合并..可以从上往下从左往右，每次只需要判断上面的点和左边的点是否有空，如果有就用并查集合并。 china点和india点特殊搞就好。
然后判断india和china是否联通，如果是则输出-1.否则从最后添加的山开始移除，每次移除一座山，添加四个方向能添加的边（注意这里不要忘记如果改点在第0行或者第n-1行还要添加和china或者india的边）
然后移除后询问india和china是否联通 （root(china)==root(india)?）
如果时间i联通了，而i+1没有联通，说明时间i是两国最早的失去联系的时间。
第一次做这种题目，这种题目的一般做法都是倒过来做。貌似还有一个二分删除的山+bfs判断连通性的。。。？ 窝再搞搞看。 update :二分+bfs判断连通性。其实这个思路更常规。。做法就是字面意思。注意无解的判断即可。
并查集解法：
/* ***********************************************
Author :111qqz
Created Time :2016年03月27日 星期日 20时11分02秒
File Name :code/bc/#77/1003.cpp
************************************************ */
1#include <cstdio>
2#include <cstring>
3#include <iostream>
4#include <algorithm>
5#include <vector>
6#include <queue>
7#include <set>
8#include <map>
9#include <string>
10#include <cmath>
11#include <cstdlib>
12#include <ctime>
13#define fst first
14#define sec second
15#define lson l,m,rt<<1
16#define rson m+1,r,rt<<1|1
17#define ms(a,x) memset(a,x,sizeof(a))
18typedef long long LL;
19#define pi pair < int ,int >
20#define MP make_pair
1using namespace std;
2const double eps = 1E-8;
3const int dx4[4]={1,0,0,-1};
4const int dy4[4]={0,-1,1,0};
5const int inf = 0x3f3f3f3f;
6const int N=505;
7char maze[N][N];
8int f[N*N];
9int n,m;
10int q;
11int p[N][N];
12int china;
13int india;
14struct node
15{
16 int x,y;
17 int id;
}shan[N*N],kong[N*N];
1int root ( int x)
2{
3 if (x!=f[x]) f[x] = root (f[x]);
4 return f[x];
5}
1void merge( int x,int y)
2{
3 int rx = root (x);
4 int ry = root (y);
5// cout<<"rx::"<<rx<<" ry::"<<ry<<endl;
6 if (rx!=ry)
7 {
8 f[rx] = ry ;
9// f[ry] = rx;
10 }
11}
1void addegg( int x,int y)
2{
3 if (x-1>=0&&maze[x-1][y]=='0') merge(p[x][y],p[x-1][y]);
4 if (x+1<n&&maze[x+1][y]=='0') merge(p[x][y],p[x+1][y]);
5 if (y-1>=0&&maze[x][y-1]=='0') merge(p[x][y],p[x][y-1]);
6 if (y+1<m&&maze[x][y+1]=='0') merge(p[x][y],p[x][y+1]);
1 if (x==0) merge(p[x][y],china); //一开始忘记更新边缘的山被移除后，点和china以及india的边了。
2 if (x==n-1) merge(p[x][y],india);
3}
4int main()
5{
6 #ifndef ONLINE_JUDGE
7 freopen("code/in.txt","r",stdin);
8 #endif
1 int T;
2 cin>>T;
3 while (T--)
4 {
5 scanf("%d %d",&n,&m);
6 for ( int i = 0 ; i < n ; i++) scanf("%s",maze[i]);
1 scanf("%d",&q);
2 for ( int i = 1 ; i <= q ; i++)
3 {
4 int x,y;
5 scanf("%d %d",&x,&y);
6 shan[i].x = x;
7 shan[i].y = y;
8 shan[i].id = i;
9// maze[x][y] = '1'; //先统计空位。
10 }
1 int cnt = 0 ;
2 ms(p,-1);
3 for ( int i = 0 ; i < n ; i++)
4 {
5 for ( int j = 0 ; j < m; j++)
6 {
7 if (maze[i][j]=='0')
8 {
9 cnt++;
10 kong[cnt].x = i ;
11 kong[cnt].y = j;
12 kong[cnt].id = i;
13 p[i][j] = cnt;
14 }
15 }
16 }
1 for ( int i = 1 ; i <= q ; i ++)
2 {
3 int x = shan[i].x;
4 int y = shan[i].y;
5 maze[x][y]='1';
6 }
7 //check kong...ok!
8 //for ( int i = 1 ; i <= cnt ; i++) cout<<"kong:"<<kong[i].x<<" "<<kong[i].y<<endl;
1 china = n*m+1;
2 india = n*m+2;
3 for ( int i = 0 ; i <= n*m+2 ; i++) f[i] = i;
4 // f[china] = china;
5 // f[india] = india;
6 // cout<<"china:"<<china<<endl;
7 // cout<<"india:"<<india<<endl;
8 for ( int j = 0 ; j < m ; j++)
9 {
10 if (maze[0][j]=='0')
11 {
12 merge(china,p[0][j]);
13 }
14 if (maze[n-1][j]=='0')
15 {
16 merge(india,p[n-1][j]);
17 }
18 }
1 for ( int i = 0 ;i < n ; i++)
2 {
3 for ( int j = 0 ; j < m ; j ++)
4 {
5 if (maze[i][j]=='1') continue;
6 if (maze[i-1][j]=='0') merge(p[i-1][j],p[i][j]);
7 if (maze[i][j-1]=='0') merge(p[i][j-1],p[i][j]);
8 }
9 }
1 if (root(china)==root(india))
2 {
3 puts("-1");
4 continue;
5 }
1 for ( int i = q ; i >= 1 ; i--)
2 {
3 int x = shan[i].x;
4 int y = shan[i].y;
1 maze[x][y] = '0';
2 addegg(x,y);
3 if (root(china)==root(india))
4 {
5 printf("%d\n",i);
6 break;
7 }
8 }
9 }
1 #ifndef ONLINE_JUDGE
2 fclose(stdin);
3 #endif
4 return 0;
5}
二分+bfs判断连通性。
/* ***********************************************
Author :111qqz
Created Time :2016年03月28日 星期一 21时12分05秒
File Name :code/hdu/5652.cpp
************************************************ */
1#include <cstdio>
2#include <cstring>
3#include <iostream>
4#include <algorithm>
5#include <vector>
6#include <queue>
7#include <set>
8#include <map>
9#include <string>
10#include <cmath>
11#include <cstdlib>
12#include <ctime>
13#define fst first
14#define sec second
15#define lson l,m,rt<<1
16#define rson m+1,r,rt<<1|1
17#define ms(a,x) memset(a,x,sizeof(a))
18typedef long long LL;
19#define pi pair < int ,int >
20#define MP make_pair
1using namespace std;
2const double eps = 1E-8;
3const int dx4[4]={1,0,0,-1};
4const int dy4[4]={0,-1,1,0};
5const int inf = 0x3f3f3f3f;
6const int N=501;
7char maze[N][N];
8int n,m;
9int q;
10bool vis[N][N];
1struct node
2{
3 int x,y;
1 bool ok ()
2 {
3 if (x>=0&&x<n&&y>=0&&y<m&&!vis[x][y]) return true;
4 return false;
5 }
6}shan[250005];
int check( int id)
{
1 for ( int i = 0 ; i < n ; i++)
2 {
3 for ( int j = 0 ; j < m ; j ++)
4 {
5 if (maze[i][j]=='1') vis[i][j] = true;
6 else vis[i][j] = false;
7 }
8 }
1 for ( int i = 1 ; i <= id ; i++)
2 {
3 int x = shan[i].x;
4 int y = shan[i].y;
5 vis[x][y] = true;
6 }
1 queue<node>q;
2 for ( int j = 0 ; j < m ; j++)
3 {
1 if (!vis[0][j])
2 {
3 node tmp;
4 tmp.x = 0;
5 tmp.y = j;
6 q.push(tmp);
7 }
8 }
1 while (!q.empty())
2 {
3 node pre = q.front();q.pop();
4 if (pre.x==n-1) return 1;
5 for ( int i = 0 ; i < 4 ; i++)
6 {
7 node nxt;
8 nxt.x = pre.x + dx4[i];
9 nxt.y = pre.y + dy4[i];
10 if (nxt.ok())
11 {
12 vis[nxt.x][nxt.y] = true;
13 q.push(nxt);
1 }
2 }
3 }
4 return 0;
5}
1int bin()
2{
3 int l = 1 ;
4 int r = q ;
5 int mid;
6 while (l<=r)
7 {
8 mid = (l+r)/2;
9 if (check(mid))
10 l = mid + 1;
11 else r = mid -1;
12 }
13 if (l>q) return -1;
14 return l;
15}
16int main()
17{
18 #ifndef ONLINE_JUDGE
19 freopen("code/in.txt","r",stdin);
20 #endif
1 int T;
2 cin>>T;
3 while (T--)
4 {
5 scanf("%d%d",&n,&m);
6 for ( int i = 0 ; i < n; i++) scanf("%s",maze[i]);
7 scanf("%d",&q);
8 for ( int i = 1 ; i <= q ; i ++) scanf("%d %d",&shan[i].x,&shan[i].y);
9 int ans = bin();
10 printf("%d\n",ans);
11 }
1 #ifndef ONLINE_JUDGE
2 fclose(stdin);
3 #endif
4 return 0;
5}