[LeetCode]Bricks Falling When Hit

图的连接性的问题，很自然地会想到用并查集。这道题的问题是我们每次erase一个1，是相当于disconnect两个node，但是并查集只支持连接两个node，而不支持disconnect，所以这里我们要想办法把disconnect变成connect。如果我们按照从头到尾的顺序disconnect的话，我们反向connect就可以达到一样的效果。具体的做法是，把所有对于要抹去的brick先从grid当中消除，之后我们反向加入brick，然后看每次并查集中对应的component的size有没有变化。由于所有在顶端的点都是自动联通的，我们设定一个super node链接所有顶端的节点。假设grid有r行c列，hits长度为n，时间复杂度O((r * c + n) * lg*(r * c))，代码如下：

	class UnionFind
	{
	public:
	UnionFind(int n)
	{
	parent = vector<int>(n, 0);
	size = vector<int>(n, 1);
	for (int i = 0; i < n; ++i)
	parent[i] = i;
	}
	void connect(int i, int j)
	{
	int rootI = root(i), rootJ = root(j);
	if(rootI == rootJ)return;
	if (size[rootI] <= size[rootJ])
	{
	parent[rootI] = rootJ;
	size[rootJ] += size[rootI];
	}
	else
	{
	parent[rootJ] = rootI;
	size[rootI] += size[rootJ];
	}
	}
	bool find(int i, int j)
	{
	return root(i) == root(j);
	}
	int getSize(int i)
	{
	int r = root(i);
	return size[r];
	}
	private:
	vector<int> parent, size;
	int root(int i)
	{
	if (i == parent[i])return i;
	int r = root(parent[i]);
	parent[i] = r;
	return r;
	}
	};
	class Solution {
	public:
	vector<int> hitBricks(vector<vector<int>>& grid, vector<vector<int>>& hits) {
	int n = grid.size(), m = n ? grid[0].size() : 0, len = hits.size();
	pair<int, int> dirs[4] = { {1, 0}, {0, 1}, {-1, 0}, {0, -1} };
	//we erase bricks first, then add them in reverse order and check connectivity
	for (auto& hit : hits)
	{
	if(!grid[hit[0]][hit[1]])
	{
	hit[0] = -1;
	hit[1] = -1;
	continue;
	}
	grid[hit[0]][hit[1]] = 0;
	}
	UnionFind uf(n * m + 1);
	for (int i = 0; i < n; ++i)
	{
	for (int j = 0; j < m; ++j)
	{
	if (grid[i][j])
	{
	int idx = i * m + j + 1;
	if (!i)uf.connect(0, idx);
	for (auto& dir : dirs)
	{
	int x = i + dir.first, y = j + dir.second;
	if (x >= 0 && x < n && y >= 0 && y < m && grid[x][y])
	uf.connect(idx, x * m + y + 1);
	}
	}
	}
	}
	vector<int> res;
	stack<int> st;
	int currSize = uf.getSize(0);
	for(int k = len - 1; k >= 0; --k)
	{
	int i = hits[k][0], j = hits[k][1];
	if(i == -1 || j == -1)
	{
	st.push(0);
	continue;
	}
	grid[i][j] = 1;
	if(!i)uf.connect(0, i * m + j + 1);
	for (auto& dir : dirs)
	{
	int x = i + dir.first, y = j + dir.second;
	if (x >= 0 && x < n && y >= 0 && y < m && grid[x][y])
	uf.connect(i * m + j + 1, x * m + y + 1);
	}
	st.push(uf.getSize(0) - currSize? uf.getSize(0) - currSize - 1: 0);
	currSize = uf.getSize(0);
	}
	while(st.size())
	{
	res.push_back(st.top());
	st.pop();
	}
	return res;
	}
	};

view raw Bricks Falling When Hit.cpp hosted with ❤ by GitHub