题目1:108. 冗余连接 (kamacoder.com)
#include<iostream>
#include<vector>
using namespace std;
int n;
vector<int> father(10001, 0);
void init() {
for(int i = 1;i <= n;i++) father[i] = i;
}
int find(int u) {
return u == father[u] ? u : father[u] = find(father[u]);
}
bool isSame(int u, int v) {
u = find(u);
v = find(v);
return u == v;
}
void join(int u, int v) {
u = find(u);
v = find(v);
if(u == v) return;
father[v] = u;
}
int main() {
cin >> n;
init();
int s, t;
for(int i = 0;i < n;i++) {
cin >> s >> t;
if(isSame(s, t)) {
cout << s << " " << t << endl;
}else {
join(s, t);
}
}
return 0;
}
题目2:109. 冗余连接II (kamacoder.com)
三种情况:入度为2的时候,有两种情况一种是删哪个都行,另一种是删掉之后可能出现环,这时候就要判断删除这个边,是否成环了
如果没有入度为2,就是成环,这个从前向后遍历,通过查并集删除删除连通的即可
#include<iostream>
#include<vector>
using namespace std;
int n;
vector<int> father(1001, 0);
void init() {
for(int i = 1;i <= n;i++) {
father[i] = i;
}
}
int find(int u) {
return u == father[u] ? u : father[u] = find(father[u]);
}
bool same(int u, int v) {
u = find(u);
v = find(v);
return u == v;
}
void join(int u, int v) {
u = find(u);
v = find(v);
if(u == v) return;
father[v] = u;
}
bool isTree(vector<vector<int>>& edge, int intnode) {
init();
for(int i = 0;i < n;i++) {
if(i == intnode) continue;
// 这里判断去掉这个边是否成环,这个实在入度为2的情况下
if(same(edge[i][0], edge[i][1])) return false;
else join(edge[i][0], edge[i][1]);
}
return true;
}
void getremovedge(vector<vector<int>>& edge) {
init();
for(int i = 0;i < n;i++) {
if(same(edge[i][0], edge[i][1])) {
cout << edge[i][0] << "" << edge[i][1] << endl;
return;
}else join(edge[i][0], edge[i][1]);
}
}
int main() {
cin >> n;
vector<vector<int>> edge;
vector<int> indgree(n + 1, 0);
for(int i = 0;i < n;i++) {
int s, t;
cin >> s >> t;
indgree[t]++;
edge.push_back({s, t});
}
vector<int> vec;
for(int i = n - 1;i >=0;i--) {
if(indgree[edge[i][1]] == 2) {
vec.push_back(i);
}
}
if(vec.size() > 0) {
if(isTree(edge, vec[0])) {
cout << edge[vec[0]][0] << " " << edge[vec[0]][1] << endl;
}else cout << edge[vec[1]][0] << " " << edge[vec[1]][1] << endl;
return 0;
}
getremovedge(edge);
return 0;
}