算法概论week6 | 684. Redundant Connection && 685. Redundant Connection II
684跟685题题型类似，区别就是，684是无向图，685是有向图。
目录
- 684
- 1.1 题目描述
- 1.2 解法一
- 1.3 解法一代码
- 1.4 解法二
- 1.5 解法二代码
- 685
- 1.1 题目描述
- 1.2 解法
- 1.3 代码
684
1.1 题目描述
1.2 解法一
第一种解法是比较传统的做法，从数组的尾端开始删除一条边，看是否能通过一次dfs访问所有的节点，如果能，则这条边就是要删除的边。
首先，先把每个节点的相邻节点表示出来：
int N = edges.size();
vector<vector<int>> my_edges(N);
for(int i = 0; i < N; i++) {
my_edges[edges[i][0] - 1].push_back(edges[i][1] - 1);
my_edges[edges[i][1] - 1].push_back(edges[i][0] - 1);
}
接着，从edges数组的尾端开始，删边并进行dfs，由于是无向图，只要被删除边的两个点能通过一次dfs访问到，就说明该边可以删除：
for(int i = edges.size() - 1; i >= 0; i--) {
int visited[2000] = {};
dfs(edges[i][0] - 1, edges[i][0] - 1, edges[i][1] - 1, my_edges, visited);
if(visited[edges[i][0] - 1] && visited[edges[i][1] - 1]) {
return edges[i];
}
}
1.3 解法一代码
class Solution {
public:
vector<int> findRedundantConnection(vector<vector<int>>& edges) {
int N = edges.size();
vector<vector<int>> my_edges(N);
for(int i = 0; i < N; i++) {
my_edges[edges[i][0] - 1].push_back(edges[i][1] - 1);
my_edges[edges[i][1] - 1].push_back(edges[i][0] - 1);
}
for(int i = edges.size() - 1; i >= 0; i--) {
int visited[2000] = {};
dfs(edges[i][0] - 1, edges[i][0] - 1, edges[i][1] - 1, my_edges, visited);
if(visited[edges[i][0] - 1] && visited[edges[i][1] - 1]) {
return edges[i];
}
}
return {};
}
void dfs(int s , int u, int v, vector<vector<int>>& my_edges, int* visited) {
if(visited[s]) return;
visited[s] = 1;
for(int i = 0; i < my_edges[s].size(); i++) {
if(s == u && my_edges[s][i] == v) {
continue;
}
dfs(my_edges[s][i], u, v, my_edges, visited);
}
return;
}
};
1.4 解法二
解法二是参考别人的代码，原文：LeetCode684冗余连接
这是并查集的算法，我还没学过，只是觉得很有意思，这个算法对每条边的两个顶点查找祖先，如果祖先相等，则说明有环，返回当前数组。找祖先的过程感觉像顺藤摸瓜，有点好玩：D
1.5 解法二代码
class Solution {
public:
vector<int> findRedundantConnection(vector<vector<int>>& edges) {
int ancestor[2000] = {};
for(int i = 0; i < edges.size(); i++) {
int u_ancestor = find_ancestor(ancestor, edges[i][0]);
int v_ancestor = find_ancestor(ancestor, edges[i][1]);
if(u_ancestor == v_ancestor) {
return {edges[i][0], edges[i][1]};
}
ancestor[u_ancestor] = v_ancestor;
}
return {};
}
int find_ancestor(int *ancestor, int u) {
int res = u;
while(ancestor[res] != 0) {
res = ancestor[res];
}
return res;
}
};
685
1.1 题目描述
1.2 解法
685题将684题的无向图换成了有向图，且边[u, v]也不再满足u < v，而满足u是v的祖先。
这题需要找到一个根节点，才能通过dfs进行判断，我们可以通过节点的入度来找根节点。如果存在入度为0的节点，则该节点就是根节点，且可删除的边一定是指向入度为2的节点的两条边之一，在删除边时可只对这两条边进行判断；如果没有入度为0的点，那么所有节点的入度都为1，这时，直接把删除的边所指向的节点作为根节点；dfs后，如果删除了的边的两个节点都被访问了，则返回这条边。
1.3 代码
class Solution {
public:
vector<int> findRedundantDirectedConnection(vector<vector<int>>& edges) {
int in_degree[2000] = {};
int out_degree[2000] = {};
int flag = 0;
int root = 0;
for(int i = edges.size() - 1; i >= 0; i--) {
in_degree[edges[i][1] - 1]++;
out_degree[edges[i][0] - 1]++;
if(in_degree[edges[i][1] - 1] == 2) {
flag = 1;
}
}
if(flag) {
for(int i = 0; i < edges.size(); i++) {
if(in_degree[i] == 0) {
root = i;
break;
}
}
}
int N = edges.size();
vector<vector<int>> my_edges(N );
for(int i = 0; i < N; i++) {
my_edges[edges[i][0] - 1].push_back(edges[i][1] - 1);
}
for(int i = edges.size() - 1; i >= 0; i--) {
if((flag && in_degree[edges[i][1] - 1] == 2) || !flag) {
int visited[2000] = {};
int s = flag ? root: edges[i][1] - 1;
if(dfs(s, edges[i][0] - 1, edges[i][1] - 1, my_edges, visited) && visited[edges[i][0] - 1] && visited[edges[i][1] - 1]) {
return edges[i];
}
}
}
return {};
}
bool dfs(int s , int u, int v, vector<vector<int>>& my_edges, int* visited) {
if(visited[s]) return false;
visited[s] = 1;
for(int i = 0; i < my_edges[s].size(); i++) {
if(s == u && my_edges[s][i] == v) {
continue;
}
if(!dfs(my_edges[s][i], u, v, my_edges, visited)) return false;
}
return true;
}
};