首页 > 其他分享 >有向图访问计数

有向图访问计数

时间:2023-10-01 16:47:31浏览次数:51  
标签:有向图 fa int 访问 ++ 计数 vector ans deg

现有一个有向图,其中包含 n 个节点,节点编号从 0 到 n - 1 。此外,该图还包含了 n 条有向边。
给你一个下标从 0 开始的数组 edges ,其中 edges[i] 表示存在一条从节点 i 到节点 edges[i] 的边。
你从节点 x 开始,通过边访问其他节点,直到你在此过程中再次访问到之前已经访问过的节点。
返回数组 answer 作为答案,其中 answer[i] 表示如果从节点 i 开始执行该过程,你可以访问到的不同节点数

一. 快慢指针 + 反向建图

class Solution {
public:
    vector<int> countVisitedNodes(vector<int>& fa) {
        int n = fa.size();
        vector<int> ans(n), vis(n);
        vector<vector<int>> g(n);
        for (int i = 0; i < n; i++) g[fa[i]].emplace_back(i); // 反向建图
        for (int t = 0; t < n; t++) {
            if (vis[t] == 1) continue;
            int l = t, r = t, s = 0;
            queue<int> q = queue<int>();
            do { l = fa[l], r = fa[fa[r]]; } while (l != r);
            do { l = fa[l], r = fa[fa[r]], s++; } while (l != r);
            do { l = fa[l], r = fa[fa[r]], ans[l] = s, vis[l] = 1, q.push(l); } while (l != r);
            while (!q.empty()) {
                int u = q.front(); q.pop();
                for (auto& v: g[u]) {
                    if (vis[v] == 1) continue;
                    ans[v] = ans[u] + 1, vis[v] = 1; q.push(v);
                }
            }
        }
        return ans;
    }
};

二. 拓扑排序 + 基环树

class Solution {
public:
    vector<int> countVisitedNodes(vector<int> &g) {
        int n = g.size();
        vector<vector<int>> rg(n); // 反图
        vector<int> deg(n);
        for (int x = 0; x < n; x++) {//建立反图和入度表
            int y = g[x];
            rg[y].push_back(x);
            deg[y]++;
        }

        // 拓扑排序,剪掉 g 上的所有树枝
        // 拓扑排序后,deg 值为 1 的点必定在基环上,为 0 的点必定在树枝上
        queue<int> q;
        for (int i = 0; i < n; i++) 
            if (deg[i] == 0)  q.push(i);
        
        while (!q.empty()) {
            int x = q.front(); q.pop();
            int y = g[x];
            if (--deg[y] == 0)  q.push(y);
        }

        vector<int> ans(n, 0);
        // 在反图上遍历树枝
        function<void(int, int)> rdfs = [&](int x, int depth) {
            ans[x] = depth;
            for (int y: rg[x]) {
                if (deg[y] == 0)  // 避免访问基环
                    rdfs(y, depth + 1);
            }
        };
        for (int i = 0; i < n; i++) {
            if (deg[i] < 1)  continue;
            vector<int> ring;
            for (int x = i;; x = g[x]) { //遍历基环
                deg[x] = -1; // 将基环上的点的入度标记为 -1,避免重复访问,当做vis使用
                ring.push_back(x); // 收集在基环上的点
                if (g[x] == i)  break;
            }
            for (int x: ring) //
                rdfs(x, ring.size()); // 为方便计算,以 ring.size() 作为初始深度
        }
        return ans;
    }
};

标签:有向图,fa,int,访问,++,计数,vector,ans,deg
From: https://www.cnblogs.com/929code/p/17738958.html

相关文章

  • python中对列表的元素进行计数
     001、方法1 借助字典统计[root@pc1test2]#lstest.py[root@pc1test2]#cattest.py##测试程序#!/usr/bin/envpython3#-*-coding:utf-8-*-list1=["aa","bb","aa","cc","aa","dd",&qu......
  • 访问者模式
    访问者模式案例引入要求1.将观众分为男生和女生,对歌手进行评价,当看完某个歌手表演后,对于歌手有不同的评价(评价的类别,有成功,失败等)。传统方式实现思路创建一个Person类,其有两个子类,分别是Man和WoMan,使用ifelse分支,去判断一个歌手的评价,成功对应成功分支,失败对应失败分支。......
  • C++中悬垂指针(delete后指针)仍然可以访问所指内存的问题
    C++中悬垂指针(delete后指针)仍然可以访问所指内存的问题在指针被delete之后,此时指针被称为空悬指针或者悬垂指针,即指向一块曾经保存数据对象,但现在已经无效的内存的指针。在C++编程中,当我们delete一个指针后,指针所指向的堆地址空间便被释放,指针值变成无效,该内存可以用于之后的内......
  • redis key 被访问后不会自动延长过期时间
    Redis的过期策略按照两个维度工作:被动过期和主动过期。被动过期:只有当有客户端尝试访问一个已经过期的key时,Redis才会删除该内容。主动过期:为了防止过期的key未被立即清理,造成内存浪费,Redis会周期性地随机检查一些key是否已经过期,如果过期,则予以删除。Redis的过期时间是静态的,......
  • nginx配置kibana访问用户名和密码认证、及无认证访问配置
    转载请注明出处:在nginx上配置kibana页面访问时,默认是采用kibana的认证,一般直接安装kibana后,是没有用户名和密码认证的。如果要在负载均衡上配置反向代理和用户认证,可按以下步骤进行配置:1.安装Nginx:首先,确保已经安装了Nginx,并且可以正常访问Kibana页面。2.生......
  • 微服务的设计涉及表的访问基本原则
    微服务的设计涉及表的访问基本原则1.微服务设计上是高于独立模块,提供服务能力的接口设计。多个微服务之间,如果涉及到访问同一个数据表的访问,更多的考虑将该表的sqlmapdao层的代码归结到某个具体的服务中,而不是在多个服务中都提供一套相同的代码,不便于表的管理。(高内聚,低耦合)其......
  • P1989 无向图三元环计数 题解
    P1989无向图三元环计数题解考虑对无向图的边定向:对于每一条无向边,度数小的点向度数大的点连边,如果读书相等则按编号大小确定。这样枚举一个\(u\),再枚举它的出点\(v\),接着枚举\(v\)的出点\(w\),如果存在一个\(w\),\(u\)向它连边,那么\((u,v,w)\),就对应了原图中的一个三......
  • 通过IPsec网络客户端无法访问服务器https
    参考:https://www.cnblogs.com/lilinwei340/p/13021864.htmlhttps://www.cnblogs.com/bulh/articles/13321437.htmlhttps://help.aliyun.com/document_detail/119749.html#:~:text=%E5%9C%A8%E9%80%9A%E8%BF%87IPsec-VPN%E8%BF%9E%E6%8E%A5%E4%BC%A0%E8%BE%93TCP%E6%B5%81%E9%87......
  • 对象转JSON 遇到的BigDecimal 科学计数法的问题,json转化字段单独处理
    问题描述:项目需要发送JSON数据,BigDecimal转成json仍然显示科学计数法,如果使用BigDecimai的toPlainString()需要将数据格式转为String,所以找了一下fastjson的自定义序列化内容,记录一下,以免以后忘记解决方案:方案一:JSONObject.toJSONString(vo,SerializerFeature.WriteBigDecimalA......
  • [洛谷]-5825排列计数-欧拉数、NTT
    目录边界对称性递推形式容斥https://www.luogu.com.cn/problem/P5825题意:我们记一个排列P的升高为\(k\)当且仅当存在\(k\)个位置\(i\)使得\(P_i<P_{i+1}\)。给定排列长度\(n\),对于所有整数\(k\in[0,n]\),求有多少个排列的升高为\(k\),\(1\leqn\leq2\times10^5\)......