php购物网站设计代码,软件开发图片,模板网站与定制开发网站的区别,女性玩具广告200元目录 无向基环树找环#xff0c;[题目](https://www.luogu.com.cn/problem/P8655)拓扑排序找环并查集找环dfs找环 内向基环树[2876. 有向图访问计数](https://leetcode.cn/problems/count-visited-nodes-in-a-directed-graph/description/)[2127. 参加会议的最多员工数](https… 目录 无向基环树找环[题目](https://www.luogu.com.cn/problem/P8655)拓扑排序找环并查集找环dfs找环 内向基环树[2876. 有向图访问计数](https://leetcode.cn/problems/count-visited-nodes-in-a-directed-graph/description/)[2127. 参加会议的最多员工数](https://leetcode.cn/problems/maximum-employees-to-be-invited-to-a-meeting/description/) 无向基环树
找环题目
给定一个图,N个点N条边只有一个环输出换上的点。
拓扑排序找环
#include bits/stdc.h
using namespace std;// 点的编号从1开始
const int N 100010;
int n;
vectorint g[N];
vectorint in, visit;void topologicalOrder() {queueint q;//把入度为1的点入队for (int i 1; i n; i) {if (in[i] 1) q.push(i), visit[i] 1;}while (q.size()) {int u q.front();q.pop();for (int v: g[u]) {in[v]--;if (in[v] 1) q.push(v), visit[v] 1;}}
}void print() {for (int i 1; i n; i) if (!visit[i]) cout i ;
}int main()
{cin n;in vectorint(n);visit vectorint(n);for (int i 1; i n; i) {int u, v;cin u v;g[u].push_back(v);g[v].push_back(u);in[u];in[v];}topologicalOrder();print();return 0;
}并查集找环
#include bits/stdc.h
using namespace std;// 并查集模板
struct DSU {std::vectorint f, siz;DSU() {}DSU(int n) {init(n);}void init(int n) {f.resize(n);std::iota(f.begin(), f.end(), 0);siz.assign(n, 1);}int find(int x) {while (x ! f[x]) {x f[x] f[f[x]];}return x;}bool same(int x, int y) {return find(x) find(y);}bool merge(int x, int y) {x find(x);y find(y);if (x y) {return false;}siz[x] siz[y];f[y] x;return true;}int size(int x) {return siz[find(x)];}
};// 点的编号从1开始
const int N 100010;
int n;
vectorint g[N];
vectorint path;void findRing(int pre, int u, int v, int index) {path[index] u;if (u v) {sort(path.begin(), path.begin() index 1);for (int i 0; i index; i) cout path[i] ;return ;}for (int j: g[u]) {if (j pre) continue;findRing(u, j, v, index 1);}
}int main()
{cin n;DSU dsu(n);path vectorint(n);for (int i 1; i n; i) {int u, v;cin u v;if (dsu.find(u) ! dsu.find(v)) {// 两个点不联通g[u].push_back(v);g[v].push_back(u);dsu.merge(u, v);} else {// u和v已经联通了那么我们在图中寻找从u到v的路径这些都是环上的点findRing(-1, u, v, 0);}}return 0;
}dfs找环
#include bits/stdc.h
using namespace std;// 点的编号从1开始
const int N 100010;
int n, idx;
vectorint g[N];
vectorint path, dfn, fa;void dfs(int u){if (dfn[u] ! 0) return ;dfn[u]idx;for(int v: g[u]){if(vfa[u]) continue;if(!dfn[v]) fa[v]u,dfs(v);else {if(dfn[v]dfn[u]) continue;path.push_back(v);for(; v ! u; vfa[v]) path.push_back(fa[v]);}} return;
}int main()
{cin n;idx 0;dfn vectorint(n 1);fa vectorint(n 1);for (int i 1; i n; i) {int u, v;cin u v;g[u].push_back(v);g[v].push_back(u);}for (int i 1; i n; i) dfs(i);sort(path.begin(), path.end());for (int v: path) cout v ;return 0;
}内向基环树
每个点有且只有一个出边
2876. 有向图访问计数
class Solution {
public:vectorint countVisitedNodes(vectorint g) {int n g.size(); //节点的个数节点的编号从0开始vectorvectorint rg(n); //反图vectorint in(n);for (int x 0; x n; x) {int y g[x];// 一条从x到y的边: x - yin[y];rg[y].push_back(x); //添加反向边到反图中}// 拓扑排序剪掉g上所有的树枝queueint q;for (int i 0; i n; i) if (in[i] 0) q.push(i);while (q.size()) {int x q.front();q.pop();int y g[x];if (--in[y] 0) q.push(y);}//答案数组, 表示的是从i点出发能访问到的节点数vectorint ans(n, 0);functionvoid(int, int) rdfs [](int x, int depth) {ans[x] depth;// 以环上的点为根通过反向边去搜树枝点// in[y]0: 树枝点for (int y: rg[x]) if (in[y] 0) rdfs(y, depth 1);};for (int i 0; i n; i) {// 0: 树枝点 -1: 基环上的点if (in[i] 0) continue;vectorint ring;for (int x i; ; x g[x]) {in[x] -1; // 基环上的点标记为-1避免重复访问ring.push_back(x);if (g[x] i) break; // 回到起点i了}for (int x: ring) rdfs(x, ring.size());}return ans;}
};2127. 参加会议的最多员工数 class Solution {
public:int maximumInvitations(vectorint favorite) {int n favorite.size();vectorint in(n);// x - yfor (int y: favorite) in[y];vectorvectorint rg(n); // 反图queueint q;for (int i 0; i n; i) if (in[i] 0) q.push(i);while (q.size()) {int x q.front();q.pop();int y favorite[x];rg[y].push_back(x);if (--in[y] 0) q.push(y);}// 在反图上搜索树枝上最深的链functionint(int) rdfs [](int x) - int {int max_depth 1;for (int son: rg[x]) max_depth max(max_depth, rdfs(son) 1);return max_depth;};int max_ring_size 0, sum_chain_size 0;for (int i 0; i n; i) {if (in[i] 0) continue;// 搜索基环上的点in[i] 0; //标记避免重复访问int ring_size 1;for (int x favorite[i]; x ! i; x favorite[x]) {in[x] 0;ring_size;}if (ring_size 2) sum_chain_size rdfs(i) rdfs(favorite[i]);else max_ring_size max(max_ring_size, ring_size);}return max(max_ring_size, sum_chain_size);}
};
文章转载自： http://www.morning.tqsmc.cn.gov.cn.tqsmc.cn http://www.morning.hgfxg.cn.gov.cn.hgfxg.cn http://www.morning.xsszn.cn.gov.cn.xsszn.cn http://www.morning.klzdy.cn.gov.cn.klzdy.cn http://www.morning.kcfnp.cn.gov.cn.kcfnp.cn http://www.morning.ynbyk.cn.gov.cn.ynbyk.cn http://www.morning.thlzt.cn.gov.cn.thlzt.cn http://www.morning.bqppr.cn.gov.cn.bqppr.cn http://www.morning.wynnb.cn.gov.cn.wynnb.cn http://www.morning.bnwlh.cn.gov.cn.bnwlh.cn http://www.morning.mqwnz.cn.gov.cn.mqwnz.cn http://www.morning.qsy36.cn.gov.cn.qsy36.cn http://www.morning.jbfjp.cn.gov.cn.jbfjp.cn http://www.morning.pmwhj.cn.gov.cn.pmwhj.cn http://www.morning.rlkgc.cn.gov.cn.rlkgc.cn http://www.morning.sqmbb.cn.gov.cn.sqmbb.cn http://www.morning.qwmdx.cn.gov.cn.qwmdx.cn http://www.morning.kztts.cn.gov.cn.kztts.cn http://www.morning.dmlsk.cn.gov.cn.dmlsk.cn http://www.morning.brwei.com.gov.cn.brwei.com http://www.morning.bzfld.cn.gov.cn.bzfld.cn http://www.morning.qlznd.cn.gov.cn.qlznd.cn http://www.morning.pkdng.cn.gov.cn.pkdng.cn http://www.morning.gwsll.cn.gov.cn.gwsll.cn http://www.morning.yprnp.cn.gov.cn.yprnp.cn http://www.morning.rbffj.cn.gov.cn.rbffj.cn http://www.morning.zympx.cn.gov.cn.zympx.cn http://www.morning.rjjjk.cn.gov.cn.rjjjk.cn http://www.morning.lkbdy.cn.gov.cn.lkbdy.cn http://www.morning.drcnn.cn.gov.cn.drcnn.cn http://www.morning.fnzbx.cn.gov.cn.fnzbx.cn http://www.morning.kpypy.cn.gov.cn.kpypy.cn http://www.morning.ygpdm.cn.gov.cn.ygpdm.cn http://www.morning.mlcnh.cn.gov.cn.mlcnh.cn http://www.morning.nrcbx.cn.gov.cn.nrcbx.cn http://www.morning.paoers.com.gov.cn.paoers.com http://www.morning.xysxj.com.gov.cn.xysxj.com http://www.morning.wjndl.cn.gov.cn.wjndl.cn http://www.morning.rnjgh.cn.gov.cn.rnjgh.cn http://www.morning.dmzqd.cn.gov.cn.dmzqd.cn http://www.morning.kjjbz.cn.gov.cn.kjjbz.cn http://www.morning.dangaw.com.gov.cn.dangaw.com http://www.morning.plkrl.cn.gov.cn.plkrl.cn http://www.morning.jrkzk.cn.gov.cn.jrkzk.cn http://www.morning.kxltf.cn.gov.cn.kxltf.cn http://www.morning.cgtrz.cn.gov.cn.cgtrz.cn http://www.morning.xsjfk.cn.gov.cn.xsjfk.cn http://www.morning.nrddx.com.gov.cn.nrddx.com http://www.morning.ccyns.cn.gov.cn.ccyns.cn http://www.morning.nlrxh.cn.gov.cn.nlrxh.cn http://www.morning.fnrkh.cn.gov.cn.fnrkh.cn http://www.morning.bnfsw.cn.gov.cn.bnfsw.cn http://www.morning.hxlch.cn.gov.cn.hxlch.cn http://www.morning.gfqjf.cn.gov.cn.gfqjf.cn http://www.morning.qzxb.cn.gov.cn.qzxb.cn http://www.morning.jphxt.cn.gov.cn.jphxt.cn http://www.morning.caswellintl.com.gov.cn.caswellintl.com http://www.morning.xqcbz.cn.gov.cn.xqcbz.cn http://www.morning.yqwsd.cn.gov.cn.yqwsd.cn http://www.morning.gwdmj.cn.gov.cn.gwdmj.cn http://www.morning.bnmrp.cn.gov.cn.bnmrp.cn http://www.morning.sjpbh.cn.gov.cn.sjpbh.cn http://www.morning.rqsr.cn.gov.cn.rqsr.cn http://www.morning.nqrlz.cn.gov.cn.nqrlz.cn http://www.morning.lkmks.cn.gov.cn.lkmks.cn http://www.morning.dhqzc.cn.gov.cn.dhqzc.cn http://www.morning.ysskn.cn.gov.cn.ysskn.cn http://www.morning.rhmpk.cn.gov.cn.rhmpk.cn http://www.morning.nhpgm.cn.gov.cn.nhpgm.cn http://www.morning.mymz.cn.gov.cn.mymz.cn http://www.morning.wmdqc.com.gov.cn.wmdqc.com http://www.morning.ghrhb.cn.gov.cn.ghrhb.cn http://www.morning.sypzg.cn.gov.cn.sypzg.cn http://www.morning.sgtq.cn.gov.cn.sgtq.cn http://www.morning.huihuangwh.cn.gov.cn.huihuangwh.cn http://www.morning.tslwz.cn.gov.cn.tslwz.cn http://www.morning.nyhtf.cn.gov.cn.nyhtf.cn http://www.morning.ktfnj.cn.gov.cn.ktfnj.cn http://www.morning.zxznh.cn.gov.cn.zxznh.cn http://www.morning.tdldh.cn.gov.cn.tdldh.cn
