题目描述

题目大意：第几步后形成了环结构

思路 （并查集）

判断无向图是否有环

怎么判断是否封闭？或者形成了一个环？

判断将要连接的两个点a,b 是否在同一个联通域中 find(a) == find(b)

细节

一维的便于处理，将二维矩阵映射到一维
x * n + y 注意x,y都是从0开始的

int get(int x, int y)  // 下标映射到一维   前提都是x y 都是从1开始的
{
    return x * n + y;
}

c++ 代码

#include <iostream>


using namespace std;

const int N = 40010;

int n, m; 
int p[N];

// 查找某个祖宗结点  优化方法采用了路径压缩  ，另外一种为按秩合并（小的接到大的上面）
int find(int x)
{
    if(p[x] != x) p[x] = find(p[x]);
    return  p[x] ;
}
// 合并两个集合
void merge(int x ,int y)
{
    p[find(x)] = find(y);
}

int get(int x, int y)  // 下标映射到一维   前提都是x y 都是从1开始的
{
    return x * n + y;
}

int main()
{
    cin >> n >> m;
    // 初始化
    for(int i = 1; i <= n * n ; i++)  p[i] = i;

    int x ,y;
    char d;
    int res = 0;

    for(int i = 1; i <= m; i ++)
    {
        cin >> x >> y >> d; //帮我们处理 空格回车 制表符
        x -- , y --; 
        int a = get(x, y);
        int b;
        if(d == 'D')  // 向下画
            b = get(x + 1, y);
        else          // 向右画
            b = get(x, y + 1);

        if(find(a) == find(b)){
            res = i;
            break;
        }
        else merge(a, b); 
    }

    if(res == 0) puts("draw");
    else cout << res << endl;

    return 0;


}

收获

• 二维下标的处理 get()
• 注意题意下标的映射 `