图论第7天

今天去打了会羽毛球。最近还是有点累啊，今天尽量效率

1971. 寻找图中是否存在路径

第一步是先整init

第二步先把该关联的关联

第三步判断是否有路

class Solution {
private:int nMax = 200005;vector<int>father = vector<int>(nMax,0);void init(int num){for(int i = 0;i < num;i++){father[i] = i;}}int find(int x){return x == father[x] ? x : father[x] = find(father[x]);}bool isSame(int a,int b){a = find(a);b = find(b);return a == b;}void join(int a ,int b){a = find(a);b = find(b);if(a == b)return;father[b] = a;}
public:bool validPath(int n, vector<vector<int>>& edges, int source, int destination) {init(n);for(int i = 0;i < edges.size();i++){join(edges[i][0],edges[i][1]);}return isSame(source,destination);}
};

684.冗余连接

其实做的事就是不断的搭桥，直到哪个用不上，就return。

class Solution {
private:int nMax = 1005;vector<int>father = vector<int>(nMax,0);void init(){for(int i = 0;i < nMax;i++){father[i] = i;}}int find(int x){return x == father[x]? x : father[x] = find(father[x]);}bool isSame(int a , int b){a = find(a);b = find(b);return a == b;}void join(int a , int b){a = find(a);b = find(b);if(a == b)return;father[b] = a;}public:vector<int> findRedundantConnection(vector<vector<int>>& edges) {init();for(int i = 0; i < edges.size();i++){if(isSame(edges[i][0],edges[i][1]))return edges[i];else join(edges[i][0],edges[i][1]);}return {};}
};

685.冗余连接II

有点难的那种，今天有点晚啦，先洗澡去啦，后面补上。