用并查集。
显而易见，划线的操作就相当于并查集中的合并，所以我们把红线和蓝线放在两个不同的区域中(1-n和n+1-2×n)，每次合并之前如果已经在同一个集合中，那么就有人获胜了。
至于具体实现，当i是单数的时候把x和y都加上n就可以了。
另外，因为这道题n的范围比较小，所以可以直接把二维的坐标转换成一维的编号，具体一点就是d(x,y)=x×(n-1)+y。

#include<bits/stdc++.h>
#define d(x,y) (x*n-n+y)
using namespace std;
int fa[160000+10],sz[160000+10];
int get(int x)
{
    if(fa[x]==x)return x;
    else return fa[x]=get(fa[x]);
}
bool merge(int x,int y)
{
    int r1=get(x),r2=get(y);
    if(r1==r2)return 0;
    if(sz[r1]<sz[r2])fa[r1]=r2,sz[r2]+=sz[r1];
    else fa[r2]=r1,sz[r1]+=sz[r2];
    return 1;
}
int main()
{
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=160000;i++)
        fa[i]=i,sz[i]=1; 
    for(int i=1;i<=m;i++)
    {
        int x,y;
        char op;
        cin>>x>>y>>op;
        if(i%2==1)x+=n,y+=n;
        if(op=='D')
        {
            if(!merge(d(x,y),d(x,y+1)))
            {
                printf("%d\n",i);
                return 0;
            }
        }
        else
        {
            if(!merge(d(x,y),d(x+1,y)))
            {
                printf("%d\n",i);
                return 0;
            }
        } 
    }
    puts("draw");
    return 0;
}