用并查集这样处理连通快为什么是错误的?
查看原帖
用并查集这样处理连通快为什么是错误的?
481621
Zhang_Wenjie楼主2024/5/24 13:14

rt,只过了 #1,7 两个点

inline void add(int x, int y, int w)
{
	e[++ top] = (edge){y, w, h[x]};
	h[x] = top;
}

int find(int x)
{
	return fa[x] == x ? x : fa[x] = find(fa[x]);
}

inline void draw()
{
	for (re i = 1; i <= n; i ++) fa[i] = i;
	
	for (re x = 1; x <= n; x ++)
		for (re i = h[x]; i; i = e[i].next)
		{
			int y = e[i].to;
			if (find(x) != find(y))
			{
				fa[find(x)] = find(y);
			}
		}
	int last = -1;
	for (re i = 1; i <= n; i ++)
	{
		if (fa[i] != last) 
		{
			last = fa[i];
			id[i] = ++ idx;
			block[idx].push_back(i);
		}
		if (fa[i] == last)
		{
			id[i] = idx;
			block[idx].push_back(i);
		}
			
	}	
}
2024/5/24 13:14
加载中...