【题目描述】

　　　　Alice和Bob玩了一个古老的游戏：首先画一个n × n的点阵（下图n = 3）。接着，他们两个轮流在相邻的点之间画上红边和蓝边：

                                                            

　　　　直到围成一个封闭的圈（面积不必为1）为止，“封圈”的那个人就是赢家。计算他们是否结束了游戏。

【题目链接】

　　　　http://ybt.ssoier.cn:8088/problem_show.php?pid=1347

【算法】　　

　　　　并查集解决的是连通性（无向图联通分量）和传递性（家谱关系）问题，并且可以动态的维护。抛开格子不看，任意一个图中，增加一条边形成环当且仅当这条边连接的两点已经联通，于是可以将点分为若干个集合，每个集合对应图中的一个连通块。

【代码】

1 #include 
     
       2 #define P pair
      
        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 }