当前位置: 首页 > article >正文

代码随想录算法营Day59 | 寻找存在的路径, 冗余连接,冗余连接II

寻找存在的路径

这题使用并查集即可。并查集加路径压缩。

#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);
}


http://www.kler.cn/a/576136.html

相关文章:

  • 用DeepSeek学Android开发:Android初学者遇到的常见问题有哪些?如何解决?
  • 分类学习(加入半监督学习)
  • c# 修改邮件附件名称
  • Flask 打包为exe 文件
  • git如何解除远程仓库 改变远程仓库地址
  • fastapi+angular就业管理系统
  • 慕慕手记项目日记 2025-3-7 项目基本环境搭建
  • 如何用FFmpeg高效拉流(避坑指南)
  • 捣鼓180天,我写了一个相册小程序
  • Zypher Network :基于零知识证明方案为 AI 赋予可信框架
  • leetcode麻烦又易忘记题目
  • Python Flask框架学习汇编
  • ReferenceError: assignment to undeclared variable xxx
  • C/C++基础知识复习(50)
  • 九、Redis 并发控制:单线程原理与 Pipeline 批量优化
  • 部署Nagios Core服務器安裝好了部署了aapenal 作為網頁服務器設定了防火墻可視化的軟件來每日監測服務器的狀況.
  • 计算机毕业设计SpringBoot+Vue.js周边游平台(源码+文档+PPT+讲解)
  • createrepo centos通过nginx搭建本地源
  • 实现NTLM relay攻击工具的Python代码示例
  • TensorFlow的pb模型