1347 格子游戏 （并查集）
【题目描述】
Alice和Bob玩了一个古老的游戏：首先画一个n × n的点阵（下图n = 3）。接着，他们两个轮流在相邻的点之间画上红边和蓝边：
直到围成一个封闭的圈（面积不必为1）为止，“封圈”的那个人就是赢家。计算他们是否结束了游戏。
【题目链接】
http://ybt.ssoier.cn:8088/problem_show.php?pid=1347
【算法】
并查集解决的是连通性（无向图联通分量）和传递性（家谱关系）问题，并且可以动态的维护。抛开格子不看，任意一个图中，增加一条边形成环当且仅当这条边连接的两点已经联通，于是可以将点分为若干个集合，每个集合对应图中的一个连通块。
【代码】
1 #include <bits/stdc++.h> 2 #define P pair<int,int> 3 #define fst first 4 #define snd second 5 using namespace std; 6 P fa[210][210]; 7 int n,m; 8 P Get(P x) 9 { 10 if(fa[x.fst][x.snd]==x) return x; 11 return fa[x.fst][x.snd]=Get(fa[x.fst][x.snd]); 12 } 13 void Merge(P x,P y) 14 { 15 P root=Get(x); 16 fa[root.fst][root.snd]=Get(y); 17 } 18 int main() 19 { 20 scanf("%d%d",&n,&m); 21 for(int i=1;i<=n;i++) 22 for(int j=1;j<=n;j++) 23 fa[i][j].fst=i,fa[i][j].snd=j; 24 for(int i=1;i<=m;i++) { 25 P x,y; char s[2]; 26 scanf("%d%d%s",&x.fst,&x.snd,s); 27 if(s[0]=='R') y.fst=x.fst,y.snd=x.snd+1; 28 else y.fst=x.fst+1,y.snd=x.snd; 29 if(Get(x)!=Get(y)) Merge(x,y); 30 else { 31 printf("%d\n",i); 32 return 0; 33 } 34 } 35 puts("draw"); 36 return 0; 37 }优质内容筛选与推荐>>
1、centos终端中mysql中文显示乱码的处理
2、MIME
3、彻底研究StringBuilder 转
4、PHP用CURL发送Content-type为application/json的HTTP/HTTPS请求
5、ExtJS 中类的选项 - config