Motion Rule (16)-Union Check Basic Questions-Grid Game

[Problem description]

Aliceand Bobplayed an old game: draw one firstn * n lattice (belown= 3) Then, the two of them take turns to draw between adjacent dotsRed and blue borders:

until a closed circle (the area does not have to be 1), the person who "closes" is the winner.Because the board is so big(n<= 200), their game is reallyis too long!They don't even know who won the game in the game.So please write a program to help them figure out if they're over the game?

[input format]

The first line of input data is two integersnandm.mindicates that a total of mlines.After mlines, each line starts with two numbers(x,y), which represents the starting point coordinates of the line, and then separate a character with a space, if the character is"D ", it is a downward connection, if it is "R" is to connect a side to the right.The input data will not have duplicate edges and is guaranteed to be correct.

[Output format]

Output a line: end at the first step.If m does not end after the step, output a line "draw".

[Sample input]

3 5

1 1 D

1 1 R

1 2 D

2 1 R

2 2 D

[Example output]

4

#include #include using namespace std;int fa[40001], n, m, x, y, r1, r2, xx, yy;char ch;int find(int u){return fa[u] == u ? u : fa[u] = find(fa[u]);}int read(){int x = 0;char ch = getchar();while (!isdigit(ch))ch = getchar();while (isdigit(ch))x = x * 10 + ch - 48, ch = getchar();return x;}int main(){cin >> n >> m;for (int i = 1; i <= n * n; i++)fa[i] = i;for (int i = 1; i <= m; i++){x = read();y = read();cin >> ch;xx = n * (x - 1) + y;if (ch == 'D')yy = xx + n;elseyy = xx + 1;r1 = find(xx);r2 = find(yy);if (r1 != r2)fa[r1] = r2;else{cout << i;return 0;}}cout << "draw" << endl;return 0;}