尋找存在的路徑

這題使用并查集即可。并查集加路徑壓縮。

#include <iostream>
using namespace std;
int find(int* father,int u){return father[u] == u ? u : father[u] = find(father,father[u]);
}bool isSame(int* father,int u,int v){return find(father,u) == find(father,v);
}void join(int* father,int u,int v){u = find(father,u);v = find(father,v);if(u == v){return;}father[v] = u;
}int main(){int N,M,source,destination,u,v;cin >> N >> M;int father[N+1];for(int i=1;i<=N;i++){father[i] = i;}for(int i=0;i<M;i++){cin >> u >> v;join(father,u,v);}cin >> source >> destination;if(isSame(father,source,destination)){cout<<1;}else{cout<<0;}
}

冗余連接

這題也是并查集問題，刪除那個導致圖存在環的邊，我們可以通過判斷新加入的邊的兩個點是否存在同一個father，如果他們是同一個father，那就說明這兩個點是已經加入圖中的點，如果在這兩個點之間加一條邊的話會導致環的產生。而如果是新加入圖的點那他們的祖先應該是不同的。

#include <iostream>
using namespace std;
int N;
int father[1001];void init(){for(int i=1;i<=N;i++){father[i] = i;}
}int find(int u){return father[u] == u ? u : father[u] = find(father[u]);
}bool isSame(int u,int v){return find(u) == find(v);
}void join(int u,int v){u = find(u);v = find(v);if(u == v) return;father[v] = u;
}
int main(){int u,v;cin >> N;init();for(int i=0;i<N;i++){cin >> u >> v;if(isSame(u,v)){printf("%d %d",u,v);break;}else{join(u,v);}}}

冗余連接II

這道題與上題邏輯類似，不過他變成了有向圖，這里需要判斷刪除的邊是否能繼續保證圖變成有向樹即除了根節點，其余的節點的入度都得是1且不存在環。所以我們需要收集那些入度為2的節點，并嘗試去刪除其中的邊，使有向圖變成一個有向樹。

#include <iostream>
#include <vector>
using namespace std;
int N;
int father[1001];void init(){for(int i=1;i<=N;i++){father[i] = i;}
}int find(int u){return father[u] == u ? u : father[u] = find(father[u]);
}bool isSame(int u,int v){return find(u) == find(v);
}void join(int u,int v){u = find(u);v = find(v);if(u == v) return;father[v] = u;
}void getRemoveEdge(vector<vector<int>>& edges){init();for(vector<int>& v : edges){if(isSame(v[0],v[1])){printf("%d %d",v[0],v[1]);return;}else{join(v[0],v[1]);}}
}bool isTreeAfterRemoveEdges(vector<vector<int>> &edges,int deleteEdge){init();for(int i=0;i<edges.size();i++){if(i==deleteEdge) continue;if(isSame(edges[i][0],edges[i][1])){return false;}join(edges[i][0],edges[i][1]);}return true;
}int main(){int u,v;vector<vector<int>> edges;cin >> N;vector<int> inDegrees(N+1,0);for(int i=0;i<N;i++){cin >> u >> v;inDegrees[v]++;edges.push_back({u,v});}vector<int> vec;for(int i = N-1;i>=0;i--){if(inDegrees[edges[i][1]] == 2){vec.push_back(i);}}if(vec.size()>0){if(isTreeAfterRemoveEdges(edges,vec[0])){printf("%d %d",edges[vec[0]][0],edges[vec[0]][1]);}else{printf("%d %d",edges[vec[1]][0],edges[vec[1]][1]);}return 0;}getRemoveEdge(edges);
}