力扣2076. 处理含限制条件的好友请求

力扣2076. 处理含限制条件的好友请求

第九十七天 --- 力扣2076. 处理含限制条件的好友请求

• 题目一
• • 思路：并查集
  • • 注意
  • 代码

题目一

力扣:2076. 处理含限制条件的好友请求

思路：并查集

1、我们先读题，最开始每个节点都没有朋友；每一个请求能够通过，那么可以建立直接联系；请求同意之前，同样还得看有没有直接不成为朋友，或者间接不成为朋友。这很明显连通分量问题，间接不能成朋友，就是；两个不能成为朋友的人在一个大的集体中。综上所述：明显的并查集！
2、并查集具体 *** 作见我的博客：力扣684冗余连接
3、我们有了并查集之后，就按照好友请求的先后顺序处理请求就行。我们本题加了限制条件，不是所有的好友请求都给通过，必须是不能让仇人们在一个连通分量才行，所以我们采取“存档”机制，即在 *** 作之前做一份存档，把当前并查集状态做一个系统快照，然后在试探着同意请求，检查仇人们在不在一个集体中即可。

注意

我们以上说的方法就是朴素的想法，做题的时候，简单分析一下朴素算法，1000数据量，O(N^2）没问题，那么我们就这么做，切记，别乱加优化。要么是算法本身不行必须优化处理，要么就先别加优化，直接朴素算法，乱加的话会适得其反。

代码

class Solution {
public:
	vector friendRequests(int n, vector>& restrictions, vector>& requests) {

		init(n);//初始化并查集

		int n_req = requests.size();
		int n_res = restrictions.size();

		this->restrictions = restrictions;

		vector ans(n_req, false);

		for (int i = 0; i < n_req; i++) {//按照顺序处理请求
			ans[i] = right_req(requests[i][0] + 1, requests[i][1] + 1, n_res);
		}
		return ans;
	}
	bool right_req(int i, int j, int n) {
		vector tmp = father;//上一次的存档
		
		merge(i, j);
		for (int k = 0; k < n; k++) {
			if (find(restrictions[k][0] + 1) == find(restrictions[k][1] + 1)) {//查看仇人在不在一起
				this->father = tmp;
				return false;
			}
		}
		return true;
	}
private:
	vector> restrictions;
	void init(int size) {//以下是并查集 *** 作
		this->size = size;
		father.resize(size + 1);
		for (int i = 0; i <= size; i++) {
			father[i] = i;
		}
	}
	vector father;
	int size;
	int find(int k) {	
		if (k <= 0 || k > size) {
			return -1;
		}
		if (father[k] == k) {
			return father[k];
		}
		father[k] = find(father[k]);
		return father[k];
	}
	void merge(int i, int j) {
		father[find(i)] = find(j);
	}
};

所有代码均以通过力扣测试
（经过多次测试最短时间为）：

时间复杂度：O(N^2)