精华内容
下载资源
问答
  • 编辑:卢凯瑞1 名词解释DAG,全称:Directed Acyclic Graph,中文:有向无环图入度:有向图中某点作为图中边的终点的次数之和出度:对于有向来说,顶点的出边条数即为该顶点的出度2 调度系统的有向无环图数据调度...

    b865b589e086a30dd0f8cf0dbb479eaa.gif

    点击上方蓝字关注DolphinScheduler(海豚调度)

    b865b589e086a30dd0f8cf0dbb479eaa.gif

    |作者:鲍亮

    |编辑:卢凯瑞

    1 名词解释

    DAG,全称:Directed Acyclic Graph,中文:有向无环图

    入度:有向图中某点作为图中边的终点的次数之和

    出度:对于有向图来说,顶点的出边条数即为该顶点的出度

    2 调度系统中的有向无环图

    数据调度系统中,多个任务之间的依赖关系,用图可以表示,如下图所示,每个顶点表示一个任务,箭头方向表示任务的执行顺序。任何顶点都无法经过边回到该顶点,则该图就是无环图,即为有向无环图(DAG图)。

    b443b5a95f6c269b286cd2775d888e4a.png

    图一

    那么在有向图中,如果有环的存在,如图示:

    68e1d311288483fabc7e5afeb7d4b683.png

    图二

    在有环的情况下,任务3的执行需要任务5完成,而5的执行又需要3,4依次执行完成,这样就会造成死循环,此调度任务永远无法成功执行。所以在调度系统中,对于无环的检测就非常重要。

    3 无环检测

    在调度系统中,检查图是否有环,分两种场景:1. 编辑图的过程中每一步操作都需要对其做无环检测;2. 对已经存在的图进行拓扑排序,检测是否有环。

    3.1 编辑时检测

    对于新创建的图来说,每增加一条边,都需要检测,这条边是否导致环的存在 思路:如图1到图2, 如果要加一条5到3的边,就从3开始遍历后续顶点,如果能回到顶点5的话就证明新加的边导致环的产生;如果不能回到5,证明新添加的边不会导致有环。检测代码如下:

    /**

    * 判断增加边(fromVertex --> toVertex)是否合法,需要判断是否符合无环的约束

    *

    * @param fromVertex     起点

    * @param toVertex       终点

    * @param createVertex 是否创建结点

    * @return

    */

    private boolean isLegalAddEdge(Vertex fromVertex, Vertex toVertex, boolean isCreate){

    if (fromVertex.equals(toVertex)) {

    logger.error("edge fromVertex({}) can't equals toVertex({})",fromVertex,toVertex);

    return false;

    }

    if (!isCreate) {

    if (!hasVertex(fromVertex) || !hasVertex(toVertex)){

    logger.error("edge fromVertex({}) or toVertex({}) is not in vertices map",fromVertex,toVertex);

    return false;

    }

    }

    Queue queue = new LinkedList<>();

    queue.add(toVertex);

    int verticesCount = getVerticesCount();

    //如果没有找到fromVertex, 表示无环;

    while (!queue.isEmpty() && verticesCount > 0) {

    verticesCount -= 1;

    Vertex key = queue.poll();

    // 遍历后续顶点

    for (Vertex subsequentVertex : getSubsequentNodes(key)) {

    if (subsequentVertex.equals(fromVertex)) {

    return false;

    }

    queue.add(subsequentVertex);

    }

    }

    return true;

    }

    3.2 拓扑排序检测

    有向图的拓扑排序,思路如下:

    遍历图中所有的顶点,将入度为0的顶点入队列(如果多个顶点入度为0,取顶点顺序可能不一样,所以此处排序结果可能是多个)。

    从队列中poll出一个顶点,更新该顶点的邻接点的入度(减1),如果邻接点的入度减1之后等于0,则将该邻接点入队列。

    一直执行第2步,直到队列为空。

    如果无法遍历完所有的结点,则意味着当前的图不是无环图。不存在拓扑排序。

    例如图1 入度出度:

    顶点

    入度

    出度

    顶点1

    0

    2

    顶点2

    1

    1

    顶点3

    1

    1

    顶点4

    2

    1

    顶点5

    1

    0

    拓扑排序流程如下:

    7f3795e399931f583c0b65c6ecec4700.png

    图三

    java实现如下:

    /**

    * 判断是否有环及拓扑排序结果

    *

    * 有向无环图(DAG)才有拓扑(topological)排序

    * 广度优先遍历的主要做法:

    *    1、遍历图中所有的顶点,将入度为0的顶点入队列。

    *    2、从队列中poll出一个顶点,更新该顶点的邻接点的入度(减1),如果邻接点的入度减1之后等于0,则将该邻接点入队列。

    *    3、一直执行第2步,直到队列为空。

    * 如果无法遍历完所有的结点,则意味着当前的图不是有向无环图。不存在拓扑排序。

    *

    *

    * @return key返回的是状态, 如果成功(无环)为true, 失败则有环, value为拓扑排序结果(可能是其中一种)

    */

    private Map.Entry> topologicalSortImpl() {

    //入度为0的结点队列

    Queue zeroIndegreeVertexQueue = new LinkedList<>();

    //保存结果

    List topoResultList = new ArrayList<>();

    //保存入度不为0的结点

    Map notZeroIndegreeVertexMap = new HashMap<>();

    //扫描所有的顶点,将入度为0的顶点入队列

    for (Map.Entry vertices : verticesMap.entrySet()) {

    Vertex vertex = vertices.getKey();

    int inDegree = getIndegree(vertex);

    if (inDegree == 0) {

    zeroIndegreeVertexQueue.add(vertex);

    topoResultList.add(vertex);

    } else {

    notZeroIndegreeVertexMap.put(vertex, inDegree);

    }

    }

    //扫描完后,没有入度为0的结点,说明有环,直接返回

    if(zeroIndegreeVertexQueue.isEmpty()){

    return new AbstractMap.SimpleEntry(false, topoResultList);

    }

    //采用topology算法, 删除入度为0的结点和它的关联边

    while (!zeroIndegreeVertexQueue.isEmpty()) {

    Vertex v = zeroIndegreeVertexQueue.poll();

    //得到相邻结点

    Set subsequentNodes = getSubsequentNodes(v);

    for (Vertex subsequentVertex : subsequentNodes) {

    Integer degree = notZeroIndegreeVertexMap.get(subsequentVertex);

    if(--degree == 0){

    topoResultList.add(subsequentVertex);

    zeroIndegreeVertexQueue.add(subsequentVertex);

    notZeroIndegreeVertexMap.remove(subsequentVertex);

    }else{

    notZeroIndegreeVertexMap.put(subsequentVertex, degree);

    }

    }

    }

    //notZeroIndegreeVertexMap如果为空, 表示没有环

    AbstractMap.SimpleEntry resultMap = new AbstractMap.SimpleEntry(notZeroIndegreeVertexMap.size() == 0 , topoResultList);

    return resultMap;

    }

    }

    输出每个顶点的同时还要删除以它为起点的边。如果图有V个顶点,E条边,则一般该算法的时间复杂度为O(V+E)。这里实现的算法最终key返回的是状态, 如果成功(无环)为true, 失败则有环, 无环时value为拓扑排序结果(可能是其中一种)。

    展开全文
  • = prev并且w已被访问了,则可以判断图中存在;假设第一访问的顶点的父节点为其本身,我们以1 为例进行讲解: 第一步:我们先访问0号顶点,此时v = 0 , prev = 0,w = 1。满足w != prev,但不满足w以访问,继续...

    一、问题描述

    如何检测无向图中的环?注意:本题中不考虑自环和平行环

    二、解决思路

    由于深度优先搜索性质,我们可以用它来检测环。假设当前访问顶点为v,访问v之前访问的顶点为prev,则prev为v的前驱节点。设w为v的后继节点,且w != prev并且w已被访问了,则可以判断图中存在环;假设第一个访问的顶点的前驱节点为其本身,我们以图1 为例进行讲解:

    第一步:我们先访问0号顶点,此时v = 0 , prev = 0,w = 1。满足w != prev,但不满足w以访问,继续执行下一步;如下图:

    第二步:我们访问1号顶点,此时v = 1,prev = 0,w = 2或3;不满足条件继续执行如下图所示:

    第三步:我们访问2号顶点,此时v = 2,prev = 1,w = 1或3;不满足条件继续执行,如下图所示:

    第四步:我们访问3号顶点,此时v = 3,prev = 2;两种情况,第一种情况:w = 2,v = 3,prev = 2不满足w != prev;第二种情况:w = 1,v = 3,prev = 2满足w != prev并且满足w已经访问,所以该图是一个有环图。

    三、算法实现

    本算法依赖上一篇文章所建立图,其图的创建代码参考上一篇文章无向图的创建(java实现),代码实现如下所示:

    package graph;
    
    import java.util.Arrays;
    
    /**
     * 通过深度优先搜索检测图中是否存在环
     *
     * @date 2021-01-22 15:18
     * @author hh
     */
    public class CycleTest {
        /**
         * 图对象
         */
        private Graph graph;
    
        /**
         * 标记哪些顶点被访问
         */
        private boolean[] marked;
    
        /**
         * 是否存在环
         */
        private boolean isHasCycle;
    
        private CycleTest() {
        }
    
        public boolean hasCycle(){
            return isHasCycle;
        }
    
        public CycleTest(Graph graph) {
            this.graph = graph;
            //默认不存在环
            this.isHasCycle = false;
            marked = new boolean[graph.getVertices()];
            Arrays.fill(marked,Boolean.FALSE);
            this.dfs();
        }
    
        /**
         * 深度优先搜索
         */
        public void dfs(){
            for(int v = 0; v < graph.getVertices(); v++ ){
                if(!isMarked(v)){
                    this.search(v,v);
                }
            }
        }
    
    
        private void search(int v,int prev){
            System.out.print(v +" ");
            marked[v] = true;
            for(Integer w : graph.adj(v)){
                if(!isMarked(w)){
                    search(w,v);
                }else if (w != prev){
                    isHasCycle = true;
                }
            }
        }
    
        /**
         * 顶点w是否被访问过
         * @param w :顶点编号
         * @return ;是否被访问
         */
        private boolean isMarked(int w){
            return this.marked[w];
        }
    }

    测试代码如下所示:

    public static void main(String[] args) throws Exception {
            String filename = "D:\\Desktop\\graph5.txt";
            Graph graph = new Graph();
            graph.createGraphByFile(filename);
            CycleTest cycleTest = new CycleTest(graph);
            boolean hasCycle = cycleTest.hasCycle();
            System.out.print("\n是否存在环:" + hasCycle);
        }

     

    展开全文
  • 有向求最小

    2021-11-19 13:48:34
    文章目录有向求最小方法1floyd方法2dijkstra方法3tarjan方法4 拓扑排序方法5 并查集求 有向求最小 方法1floyd 三重循环扫一遍,然后 rep(i,1,n){ if(d[i][i]==inf) continue; ans=min(ans,d[i][i]); } ...

    有向图求最小环

    习题P2661

    方法1floyd

    三重循环扫一遍,然后

    rep(i,1,n){
        if(d[i][i]==inf) continue;
    	ans=min(ans,d[i][i]);
    }
    

    时间复杂度: O ( n 3 ) O(n^3) O(n3)

    方法2dijkstra

    对每个结点 d i j k s t r a dijkstra dijkstra一次。

    思想与 f l o y d floyd floyd类似。

    时间复杂度: O ( n ( n + m ) l o g n ) O(n(n+m)logn) O(n(n+m)logn)

    方法3tarjan

    找强连通分量的大小,对所有 > 1 >1 >1的取 m i n min min即可。

    // Problem: P2661 [NOIP2015 提高组] 信息传递
    // Contest: Luogu
    // URL: https://www.luogu.com.cn/problem/P2661
    // Memory Limit: 125 MB
    // Time Limit: 1000 ms
    // Date: 2021-11-19 13:11:49
    // --------by Herio--------
    
    #include<bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    typedef unsigned long long ull; 
    const int N=2e5+5,M=2e4+5,inf=0x3f3f3f3f,mod=1e9+7;
    const int hashmod[4] = {402653189,805306457,1610612741,998244353};
    #define mst(a,b) memset(a,b,sizeof a)
    #define PII pair<int,int>
    #define PLL pair<ll,ll>
    #define x first
    #define y second
    #define pb emplace_back
    #define SZ(a) (int)a.size()
    #define rep(i,a,b) for(int i=a;i<=b;++i)
    #define per(i,a,b) for(int i=a;i>=b;--i)
    #define IOS ios::sync_with_stdio(false),cin.tie(nullptr) 
    void Print(int *a,int n){
    	for(int i=1;i<n;i++)
    		printf("%d ",a[i]);
    	printf("%d\n",a[n]); 
    }
    template <typename T>		//x=max(x,y)  x=min(x,y)
    void cmx(T &x,T y){
    	if(x<y) x=y;
    }
    template <typename T>
    void cmn(T &x,T y){
    	if(x>y) x=y;
    }
    int n;
    struct edge{
    	int to,nt;
    }e[N<<1];
    int s[N],tp,cnt,h[N];
    void add(int u,int v){
    	e[++cnt]={v,h[u]},h[u]=cnt;
    }
    int vis[N],dfn[N],low[N],id;
    int ans;
    void dfs(int u,int fa){
    	dfn[u]=low[u]=++id;vis[u]=1;s[++tp]=u;
    	for(int i=h[u];i;i=e[i].nt){
    		int v=e[i].to;
    		if(!dfn[v]){
    			dfs(v,u);
    			low[u]=min(low[u],low[v]);
    		}else if(v!=fa){
    			low[u]=min(low[u],dfn[v]);
    		}
    	}
    	if(dfn[u]==low[u]){
    		int sum=1;
    		while(s[tp]!=u){
    			vis[s[tp--]]=0,sum++;
    		}
    		tp--;
    		if(sum==2){
    			puts("2");exit(0);
    		}
    		if(sum>1) ans=min(ans,sum);
    	}
    }
    int main(){
    	scanf("%d",&n);
    	rep(i,1,n){
    		int x;scanf("%d",&x);
    		add(i,x);
    	}
    	ans=inf;
    	rep(i,1,n) if(!dfn[i]) dfs(i,0);
    	printf("%d\n",ans);
    	return 0;
    }
    

    方法4 拓扑排序

    从所有入度为0的点开始 b f s bfs bfs,然后标记,显然这些点不可能组成环,然后再对没有标记的点进行暴力 d f s dfs dfs找环,不断取 m i n min min即可。

    方法5 并查集求环

    #include<cstdio>
    #include<iostream>
    using namespace std;
    int f[200002],d[200002],n,minn,last;   //f保存祖先节点,d保存到其祖先节点的路径长。 
    int fa(int x)
    {
        if (f[x]!=x)                       //查找时沿途更新祖先节点和路径长。 
        {
            int last=f[x];                 //记录父节点(会在递归中被更新)。 
            f[x]=fa(f[x]);                 //更新祖先节点。 
            d[x]+=d[last];                 //更新路径长(原来连在父节点上)。 
        }
        return f[x];
    }
    void check(int a,int b)
    {
        int x=fa(a),y=fa(b);               //查找祖先节点。 
        if (x!=y) {f[x]=y; d[a]=d[b]+1;}   //若不相连,则连接两点,更新父节点和路径长。 
        else minn=min(minn,d[a]+d[b]+1);   //若已连接,则更新最小环长度。 
        return;
    }
    int main()
    {
        int i,t;
        scanf("%d",&n);
        for (i=1;i<=n;i++) f[i]=i;         //祖先节点初始化为自己,路径长为0。 
        minn=0x7777777;
        for (i=1;i<=n;i++)
        {
            scanf("%d",&t);
            check(i,t);                    //检查当前两点是否已有边相连接。 
        }
        printf("%d",minn);
        return 0;
    }
    

    有向图最大环

    同理也可以用上述方法求有向图最大环。

    P5145

    其实 n n n n n n条出边的有向图就是基环树森林。

    可以用 d f s dfs dfs解决。

    #include <bits/stdc++.h>
    using namespace std;
    
    #define reg register 
    const int N = 100000 + 5;
    
    int n, d[N], t[N], a[N], b[N], ans, st;
    
    void dfs(int x, int sum) {
        if (x==st) { ans=max(ans, sum); return; }
        if (a[x] || b[x])return;
        a[x]=1; dfs(d[x], sum+t[x]); a[x]=0;
    }
    
    int main() {
        scanf("%d", &n);
        for (reg int i=1; i<=n; ++i) scanf("%d%d", &d[i], &t[i]);
        for (st=1; st<=n; ++st) dfs(d[st], t[st]), b[st]=1;
        printf("%d\n", ans);
        return 0;
    }
    
    

    用tarjan也很好写,把边权赋给源点即可。

    #include <iostream>
    #include <cstdio>
    #include <cstring>
    #include <algorithm>
    #define MAXN 1000100
    struct Edge {
        int v, nx;
    }e[MAXN];
    inline int min(int a, int b) {
        if (a < b) return a;
        else return b;
    }
    inline int max(int a, int b) {
        if (a > b) return a;
        else return b;
    }
    int head[MAXN], tim, st[MAXN], top, ecnt, n, m, x, y, dfn[MAXN], low[MAXN], in[MAXN], si[MAXN], num, se[MAXN], ans;
    bool vis[MAXN];
    void add(int f, int t) {
        e[++ecnt] = (Edge) {t, head[f]};
        head[f] = ecnt;
    }
    void tarjan(int u) {
        dfn[u] = low[u] = ++tim;
        st[++top] = u;
        vis[u] = 1;
        for (int i = head[u]; i; i = e[i].nx) {
            int v = e[i].v;
            if (!dfn[v]) {
                tarjan(v);
                low[u] = min(low[v], low[u]);
            }
            else if (vis[v]) low[u] = min(low[u], dfn[v]);
        }
        if (low[u] == dfn[u]) {
            int v;
            num++;
            do {
                v = st[top--];
                in[v] = num;
                vis[v] = 0;
                si[num] += se[v];
            } while (u != v);
        }
    }
    int main() {
        scanf("%d", &n);
        for (int i = 1; i <= n; i++) {
            scanf("%d%d", &x, &y);
            add(i, x);
            se[i] = y;
        }
        for (int i = 1; i <= n; i++) {
            if (!dfn[i]) tarjan(i);
        }
        for (int i = 1; i <= num; i++) {
            ans = max(ans, si[i]);
        }
        printf("%d\n", ans);
        return 0;
    }
    

    也可以用拓扑排序后,暴力找环即可。

    #include<bits/stdc++.h>
    using namespace std;
    int n,ans,idx;
    int head[100010],ru[100010];
    struct node{
    	int nxt,to,w;
    }edge[100010];
    void add(int u,int v,int w)
    {
    	edge[++idx].nxt=head[u];
    	edge[idx].to=v;
    	edge[idx].w=w;
    	head[u]=idx;
    }
    void topo(){
    	queue<int> q;
    	for(int i=1;i<=n;i++)
    	{
    		if(!ru[i])
    		q.push(i);
    	}
    	while(q.size())
    	{
    		int x=q.front();
    		q.pop();
    		for(int i=head[x];i;i=edge[i].nxt)
    		{
    			int v=edge[i].to;
    			ru[v]--;
    			if(!ru[v])
    			{
    				q.push(v);
    			}
    		}
    	}
    }
    void dfs(int x,int len)
    {
    	if(!ru[x])
    	{
    		ans=max(ans,len);
    		return ;
    	}
    	ru[x]--;
    	for(int i=head[x];i;i=edge[i].nxt)
    	{
    		int v=edge[i].to;
    		dfs(v,len+edge[i].w);
    	}
    }
    int main()
    {
    	cin>>n;
    	for(int i=1;i<=n;i++)
    	{
    		int d,w;
    		cin>>d>>w;
    		add(i,d,w);
    		ru[d]++; 
    	}
    	topo();//拓扑完之后还有入度的点就是在环上的
    	for(int i=1;i<=n;i++)
    	{
    		if(ru[i])
    		{
    			dfs(i,0);
    		}
    	}
    	cout<<ans;
    	return 0;
    }
    

    CF1217D

    有向图的边染色,使得环边不同为一种颜色的最小颜色种数,并输出边的颜色。

    显然答案为1或2,无环为 1,有环为2,染色可以用 d f s dfs dfs染色,或者拓扑后直接 u < v u<v u<v的边染黑, u > v u>v u>v染白,因为环肯定包括这两种情况。

    C. Cyclic Coloring

    有向图结点染色,保证 ( u , v ) (u,v) (u,v) c o l v = c o l u + 1 col_v=col_u+1 colv=colu+1,如果用 k k k种颜色的话, k k k的下一个颜色是 1 1 1,求最大 k k k

    显然对于长为 c n t cnt cnt的环, k ∣ c n t k|cnt kcnt

    对于两条起点和终点相同的链: k ∣ ( c n t 1 − c n t 2 ) k|(cnt_1-cnt_2) k(cnt1cnt2)

    为了方便处理情况 2 2 2,不妨对每个有向边建立边权为 − 1 -1 1的反边,这样就可以转换为情况1。

    然后就 d f s dfs dfs找环即可。

    #include <algorithm>
    #include <cstring>
    #include <cstdlib>
    #include <cstdio>
    #define N 200010
    #define For(i,x,y) for (i=x;i<=y;i++)
    using namespace std;
    int i,j,k,n,m,x,y,an,t;
    int a[N],next[N],head[N],b[N],f[N],v[N];
    inline void add(int x,int y) {
    	a[++t]=y,b[t]=1,next[t]=head[x],head[x]=t;
    	a[++t]=x,b[t]=-1,next[t]=head[y],head[y]=t;
    }
    void dfs(int x,int y) {
    	if (v[x]) {
    		an=__gcd(an,f[x]-y);
    		return;
    	}
    	v[x]=1; f[x]=y;
    	int v;
    	for (v=head[x];v;v=next[v]) dfs(a[v],y+b[v]);
    }
    int main() {
    	scanf("%d%d",&n,&m);
    	For(i,1,m) scanf("%d%d",&x,&y),add(x,y);
    	For(i,1,n) if (!v[i]) dfs(i,0);
    	if (an<0) an=-an;
    	if (!an) an=n;
    	printf("%d\n",an);
    	return 0;
    }
    
    

    P1477 [NOI2008] 假面舞会

    这题和上面那场183C的题好像,这题也是染色,求最大 k k k和最小 k k k

    如果有环的时候,显然最大就是所有环的 g c d gcd gcd,最小就是 g c d gcd gcd的最小因子 ( d i v ≥ 3 ) (div\ge 3) (div3)

    否则最大就是连通分量的最大链之和,最小是3。

    注意判 < 3 <3 <3的情况。

    // Problem: P1477 [NOI2008] 假面舞会
    // Contest: Luogu
    // URL: https://www.luogu.com.cn/problem/P1477
    // Memory Limit: 125 MB
    // Time Limit: 1000 ms
    // Date: 2021-11-19 16:03:15
    // --------by Herio--------
    
    #include<bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    typedef unsigned long long ull; 
    const int N=1e5+5,M=1e6+5,inf=0x3f3f3f3f,mod=1e9+7;
    const int hashmod[4] = {402653189,805306457,1610612741,998244353};
    #define mst(a,b) memset(a,b,sizeof a)
    #define PII pair<int,int>
    #define PLL pair<ll,ll>
    #define x first
    #define y second
    #define pb emplace_back
    #define SZ(a) (int)a.size()
    #define rep(i,a,b) for(int i=a;i<=b;++i)
    #define per(i,a,b) for(int i=a;i>=b;--i)
    #define IOS ios::sync_with_stdio(false),cin.tie(nullptr) 
    void Print(int *a,int n){
    	for(int i=1;i<n;i++)
    		printf("%d ",a[i]);
    	printf("%d\n",a[n]); 
    }
    template <typename T>		//x=max(x,y)  x=min(x,y)
    void cmx(T &x,T y){
    	if(x<y) x=y;
    }
    template <typename T>
    void cmn(T &x,T y){
    	if(x>y) x=y;
    }
    int n,m,cnt,h[N],vis[N];
    struct edge{
    	int to,nt,w;
    }e[M<<1];
    void add(int u,int v,int w){
    	e[++cnt]={v,h[u],w},h[u]=cnt;
    	e[++cnt]={u,h[v],-w},h[v]=cnt;
    }
    int ans,f[N],mx,mn;
    int sum;
    void dfs(int u,int d){
    	if(vis[u]){
    		ans=__gcd(ans,d-f[u]);
    		return;
    	}vis[u]=1,f[u]=d;
    	for(int i=h[u];i;i=e[i].nt){
    		int v=e[i].to;
    		dfs(v,d+e[i].w);
    	}
    	cmn(mn,d),cmx(mx,d);
    }
    int main(){
    	scanf("%d%d",&n,&m);
    	rep(i,1,m){
    		int u,v;scanf("%d%d",&u,&v);add(u,v,1);
    	}
    	rep(i,1,n){
    		if(!vis[i]){
    		mn=inf,mx=-inf;
    		dfs(i,0);
    		sum+=mx-mn+1;
    		}
    	}ans=abs(ans);
    	if(ans){
    		if(ans<3) return puts("-1 -1"),0;
    		int res;
    		for(int i=3;i<=ans;i++) if(ans%i==0) {
    			res=i;break;
    		}printf("%d %d\n",ans,res);
    	}
    	else {
    		if(sum<3) return puts("-1 -1"),0;
    		printf("%d 3\n",sum);
    	}
    	return 0;
    }
    
    

    总结以下上面两题,都是利用建立反边权,将起点和终点相同路径转换为环处理。

    有向图判负环

    1.spfa判入队次数

    当入队次数 ≥ n \ge n n 出现负环。

    但是此方法极端数据会被卡,因为最坏 n 2 n^2 n2的点入队。

    因此考虑再开一个数组表示最短路径边数,当最短路径边数 > = n >=n >=n 显然出现重复点,即环。

    2.bellman-ford判负环

    在这里插入图片描述

    时间复杂度: O ( n m ) O(nm) O(nm)

    注: d i j k s t r a dijkstra dijkstra不能判负环。

    展开全文
  • 检查_有向&无向图中

    千次阅读 2021-12-17 14:05:45
    有向图中检查环 python(递归,迭代) c++ 无向图中检查环 python(递归,迭代) c++ 1.1 python 递归: 有向中环检测:核心思想是检测节点的邻居是否再已有的stack里面 from collections import ...

    目录:

    1. 有向图中检查环
      1. python(递归,迭代)
      2. c++ [递归]
    2. 无向图中检查环
      1. python(递归,迭代)
      2. python [并查集]
      3. c++ [并查集]
      4. c++ [递归,迭代]

    1.1 python 递归: 有向图中环检测:核心思想是检测节点的邻居是否再已有的stack里面

    时间复杂度为DFS的复杂度O(V+E),空间复杂度为O(V)

    DFS solution:an edge that is from a node to itself(selfloop) or one of its ancestor;

    from collections import defaultdict
    
    # 有向图查环
    class UGraph:
        "undirected graph recursion"
        def __init__(self, vertices):
            self.V = vertices
            self.graph = defaultdict(list)
    
        def addEdge(self, u, v):
            self.graph[u].append(v)
    
        def isCyclicUtil(self, v, visited, recStack):
            """核心思想:检查节点的邻居有没有还在之前的stack里面,有则出线环"""
            visited[v] = True
            recStack[v] = True
            for neighbour in self.graph[v]:
                if visited[neighbour] == False:
                    if self.isCyclicUtil(neighbour, visited, recStack) == True:
                        return True
                elif recStack[neighbour] == True:
                    return True
    
            recStack[v] = False
            return False
    
        def isCycle(self):
            visited = [False] * (self.V + 1)
            resStact = [False] * (self.V + 1)
            for node in range(self.V):
                if visited[node] == False:
                    if self.isCyclicUtil(node, visited, resStact) == True:
                        return True
                return False
    
    
    if __name__ == "__main__":
        g = UGraph(4)
        g.addEdge(1, 2)
        g.addEdge(2, 3)
        g.addEdge(3, 1)
        g.addEdge(0, 1)
    
        print(g.isCycle())
    
    # True

    c++ (递归)

    #include <iostream>
    #include <list>
    
    using namespace std;
    
    class Graph {
        int V; // No. of vertices
        list<int> *adj;  // pointer to an array containing adjacency lists
        bool isCyclicUtil(int v, bool visited[], bool *rs);
    
    public:
        Graph(int V);  // Constructor
        void addEdge(int v, int w); // add an edge to graph
        bool isCyclic(); // return true or false
    };
    
    
    Graph::Graph(int V) {
        this->V = V;
        adj = new list<int>[V];
    }
    
    void Graph::addEdge(int v, int w) {
        adj[v].push_back(w);
    }
    
    bool Graph::isCyclicUtil(int v, bool visited[], bool *recStack) {
        if (visited[v] == false) {
            // Mark the current node as visited and part of recursion stack
            visited[v] = true;
            recStack[v] = true;
            // recur for all vertices adjacent to this vertex
            list<int>::iterator i;
            for (i = adj[v].begin(); i != adj[v].end(); ++i) {
                if (!visited[*i] && isCyclicUtil(*i, visited, recStack))
                    return true;
                else if (recStack[*i])
                    return true;
            }
        }
        recStack[v] = false;
        return false;
    }
    
    
    bool Graph::isCyclic() {
        // Mark all the vertices as not visited and not part of recursion stack
        bool *visited = new bool[V];
        bool *recStack = new bool[V];
        for (int i = 0; i < V; i++) {
            visited[i] = false;
            recStack[i] = false;
        }
        // recursive function DFS
        for (int i = 0; i < V; i++) {
            if (isCyclicUtil(i, visited, recStack)) {
                return true;
            }
        }
        return false;
    
    }
    
    
    int main()
    {
        // Create a graph given in the above diagram
    //    Graph g(4);
    //    g.addEdge(0, 1);
    //    g.addEdge(0, 2);
    //    g.addEdge(1, 2);
    //    g.addEdge(2, 0);
    //    g.addEdge(2, 3);
    //    g.addEdge(3, 3);
    
        Graph g(4);
        g.addEdge(0, 1);
        g.addEdge(0, 2);
        g.addEdge(2, 3);
    
    
        if(g.isCyclic())
            cout << "Graph contains cycle";
        else
            cout << "Graph doesn't contain cycle";
        return 0;
    }
    
    # Graph doesn't contain cycle

    2. 无向图中检查环

     

    2.1 python 版本(递归版本)

    
    # 无向图 - DFS 递归
    from collections import defaultdict
    
    class Graph:
        def __init__(self, vertices):
            self.V = vertices
            self.graph = defaultdict(list)
    
        def addEdge(self, v, w):
            self.graph[v].append(w)
            self.graph[w].append(v)
    
    
        def isCyclicUtil(self, v, visited, parent):
            visited[v] = True
            for i in self.graph[v]:
                if visited[i] == False:
                    if (self.isCyclicUtil(i, visited, v)):
                        return True
                elif i != parent:
                    return True
            return False
    
        def isCyclic(self):
            visited = [False] * (1 + self.V)
            for i in range(self.V):
                if visited[i] == False:
                    if (self.isCyclicUtil(i, visited, -1) == True):
                        return True
            return False
    
    
    if __name__ == "__main__":
        # recursive
        # g = Graph(5)
        # g.addEdge(0, 1)
        # g.addEdge(0, 2)
        # g.addEdge(2, 3)
        # g.addEdge(2, 4)
        # # g.addEdge(3, 4)
    
        g = Graph(3)
        g.addEdge(0, 1)
        g.addEdge(0, 2)
        g.addEdge(1, 2)
        print(g.isCyclic())
    
    

    c++ (递归)

    
    // c++ 无向图 - 环  - 递归
    #include <iostream>
    #include <list>
    using namespace std;
    
    // class definition
    class Graph {
        int V; // number of vertices
        list<int> *adj;  // Pointer to an array
        bool isCyclicUtil(int v, bool visited[], int parent);
    
    public:
        // Constructor
        Graph(int V);
    
        // add edge
        void addEdge(int v, int w);
    
        // return true if there is a cycle in undirected
        bool isCyclic();
    };
    
    Graph::Graph(int V) {
        this->V = V;
        adj = new list<int>[V];
    }
    
    void Graph::addEdge(int v, int w) {
        adj[v].push_back(w);
        adj[w].push_back(v);
    }
    
    
    bool Graph::isCyclicUtil(int v, bool visited[], int parent) {
        visited[v] = true;
        list<int>::iterator i;
        for (i = adj[v].begin(); i != adj[v].end(); ++i) {
            if (!visited[*i]) {
                if (isCyclicUtil(*i, visited, v))
                    return true;
            } else if (*i != parent)  // if an adjacent vertex is visited and is not parent of current vertex, then there exists a cycle
                return true;
        }
        return false;
    }
    
    
    bool Graph::isCyclic() {
        bool *visited = new bool[V];
        for (int i = 0; i < V; i++) {
            visited[i] = false;
        }
    
        for (int u = 0; u < V; u++){
            if (!visited[u])
                if (isCyclicUtil(u, visited, -1))
                    return true;
        }
        return false;
    }
    
    int main() {
        Graph g1(5);
        g1.addEdge(0, 1);
        g1.addEdge(0, 2);
        g1.addEdge(2, 3);
        g1.addEdge(2, 4);
    //    g1.addEdge(3, 4);
        g1.isCyclic()? cout << "graph contains cycle\n":cout << "graph doesn't contain cycle\n";
    }
    
    

    2.2 python 并查集

    
    # 无向图 -> 并查集
    # Find, Connect, Union
    # reference:https://github.com/azl397985856/leetcode/blob/master/thinkings/union-find.md
    
    class UF:
        """也非常容易判断是否2个节点是否连通"""
        def __init__(self, M):
            self.parent = {}  #
            self.size = {}  # 哈希表,记录每个连通域大小, key 根,value是大小
            self.cnt = 0  # 有多少个连通域
            for i in range(M):
                self.parent[i] = i
                self.cnt += 1
                self.size[i] = 1
    
    
        def find(self, x):
            """向上查找根节点, 递归(路径压缩) or 迭代"""
            # 迭代
            # while x != self.parent[x]:
            #     x = self.parent[x]
            # return x
            # 递归
            if x != self.parent[x]:
                self.parent[x] = self.find(self.parent[x])
                return self.parent[x]
            return x
    
    
        def connected(self, p, q):
            """祖先相同,则联通在一起"""
            return self.find(p) == self.find(q)
    
        def union(self, p, q):
            if self.connected(p, q):
                return
            # 小树挂大树
            leader_p = self.find(p)
            leader_q = self.find(q)
            if self.size[leader_p] < self.size[leader_q]:
                self.parent[leader_p] = leader_q
                self.size[leader_q] += self.size[leader_p]
            else:
                self.parent[leader_q] = leader_p
                self.size[leader_p] += self.size[leader_q]
            self.cnt -= 1
    
    
    class Solution:
        def findRedundantConnection(self, edges):
            uf = UF(1001)
            for fr, to in edges:
                if uf.connected(fr, to):
                    return [fr, to]
                uf.union(fr, to)
    
    
    
    
    if __name__ == "__main__":
        s = Solution()
        print(s.findRedundantConnection([[1,2], [1,3], [2,3]]))
        # print(s.findRedundantConnection([[1,2], [1,3], [1,4], [1, 5], [4, 5]]))
    

    2.3 C++ 版本(并查集检测环 - 684. 冗余连接

    
    // c++ 并查集
    class Solution{
    public:
    
        // find path and return node (represent this set),
        static int find(int n, vector<int>& rp){
            int num = n;
            while (rp[num] != num)
                num = rp[num];
            return num;
        }
    
        vector<int> findRedundantConnection(vector<vector<int>>& edges){
            vector<int> rp(1001);
            int sz = edges.size();
            // init single node set, now node is represent set
            for (int i = 0; i < sz; i++)
                rp[i] = i;
            for (int j = 0; j < sz; j++) {
                // find two node represent node
                int set1 = find(edges[j][0], rp);
                int set2 = find(edges[j][1], rp);
                if (set1 == set2)  // represent is same, cycle
                    return edges[j];
                else
                    rp[set1] = set2;
            }
            return {0, 0};
        }
    
    };
    
    void print(std::vector<int> const &input)
    {
        for (int i : input) {
            std::cout << i << ' ';
        }
    }
    
    int main() {
        Solution S =  Solution();
        vector<int> one;
        vector<vector<int>> input0 ={{1, 2}, {1, 3}, {1, 4}};
        vector<vector<int>> input1 ={{1, 2}, {1, 3}, {2, 3}};
        vector<vector<int>> input2 ={{1,2}, {2,3}, {3,4}, {1,4}, {1,5}};
        one = S.findRedundantConnection(input0);
    
        print(one);
    }
    

    展开全文
  • 在一个有向图中

    2021-08-05 20:14:27
    在一个有向图中 有向图中边的分类 树边(Tree Edge):从一个顶点指向其未访问过的子节点的边。 前向边(Forward Edge):从一个顶点指向该顶点的一个非子顶点后裔的边,且接受点被访问过。 回边(Back Edge)...
  • 业务场景调度系统的任务可视化界面需要完成用户可在界面上连线作为任意两个job间的依赖关系,也就是DAGDAG也就是有向无环图,有向无环图指的是一个无回路的有向是一条至少含有一条边且起点和终点相同的路径...
  • 的每个点有且仅有一条出边,那么从某一个点出发,沿着单向边不断移动,最终必然会进入一个环中,题目要求为,检查图中是否存在一个所有单向边方向一致的。 class Solution { public: bool circularArrayLoop...
  • 从解决一个更简单的问题开始:给定一个DAG的两个点A和B,你能...在这种情况下,因为是无的,所以没有路径。在假设A和B是不同的。WOLOG假设A有两个邻居C和D,它们都不是B。从A到B的路径数必须等于从C到B的路...
  • PIPI有一个有向,他想让你判断图中是否有,数据结构基础扎实的你能不能帮帮PIPI呢? 输入: 第一行两个整数n ,m 代表图中的结点数量和边的数量。 接下来m行,每行输入两个整数 a b 代表a有一条指向b的单向边。 ...
  • 关键字:DAG,有向无环图,算法,背包,深度优先搜索,栈,BlockChain,区块链图图是数据结构最为复杂的一种,我在上大学的时候,的这一章会被老师划到考试范围之外,作为我们的课后兴趣部分。但实际上,在...
  • 无向判断

    2021-05-06 20:39:12
    并查集通常是一维数组,数组下标表示图中节点的序号,数组的元素代表其下标对应节点的前置节点在数组下标。如所示:         并查集有两个基本操作1.找到指定节点的根节点。2.对两个不同...
  • 给定一个有向无环图$G=(V,E)$,边权重为实数,给定图中的两个顶点$k,t$,设计动态规划算法,求从k到t的最长简单路径,子问题是怎样的?算法的效率如何?算法分析:该问题不能够用贪心求解,假设从k出发,每一步...
  • 我想知道如何得到给定G的所有这些最小切结点在扩展,如何得到基数k的所有节点割集?在我想不出一种算法能有效地计算出这一点。它是否有比简单的方法更好的方法,即尝试k个节点的每个组合,并检查G是否断开连接?...
  • 检查一个有向是否存在要比无向复杂。(有向为什么比无向图检查环复杂呢?)现实管网会存在吗?管网是有方向的,理论上也是无的。arcgis有向无环图最短路径。有向无环图和二叉树的关系:如何确定父节点和...
  • 图论:有向的环路检测和取 的相关概念 顶点 边(有向、无向) 度(入度、出度) 一个顶点如果有一条边指向它,那我们就说这个顶点的入度为1 ;类似地,从顶点出发,有一条边我们就说这个顶点的出度为 1 的...
  • 无向图中,给定一些边,然后判断这些边组成的是否有。注意这个方法必须保证没有输入重边 对于一条边用(a, b)表示,然后把a,b加入到并查集中。如果又加入了一条边(b ,c) ,那么如果这个时候又需要加入一条边(c,...
  • //并查集 查找 public class DisjointSet { static int VERTICES=6;//定义顶点的个数 //初始化parent数组(找根节点用的),rank数组(减少找根节点操作,使深度最低用的) public static void init(int...
  • 判断链表是否有

    2021-09-17 10:15:20
    所示,所谓链表,一定是第一种情况,不会是第二种情况(因为每个结点仅有一个next,不会出现分叉的情况)。 题目链接:NC4 判断链表是否有 2.解题思路 明白所谓的“链表有”后,就可以根据“链表有...
  • 首先,关于单链表,一般涉及到以下问题:1.给一个单链表,判断其中是否有的存在;2.如果存在,找出的入口点;3.如果存在,求出上节点的个数;4.如果存在,求出链表的长度;5.如果存在,求出上...
  • 在一般的图中,最长路径问题不具有如最短问题一样的最优子结构属性(算法导论动态规划章节P218) 在最长路径问题,子问题是相关的 求解一个子问题会对另一个子问题产生影响 在最短路径问题,子问题是无关的 ...
  • 有向无环图及其应用

    2020-12-20 16:22:02
    在有向无环图中判断工程是否能完成 1.说明 采用了邻接表存储树结构 运用了栈来存储所有入度为0的元素下标,在出栈时将他们输出并遍历减少所有与他们相连的点的入度 2.代码 void topologicalsort(Graph*g) { //...
  • 有向无环图的所有拓扑排序 对有向无环图DAG的拓扑排序是顶点的线性排序,从而使每一有向边[u,v][u,v][u,v],顶点u进来的顺序v在。如果不是 DAG,则无法对图进行拓扑排序。 给定一个 DAG,打印的所有拓扑排序。 ...
  • 三元计数和四元计数问题 无向三元计数问题 根号分治 bitset 无向四元计数问题 有向三四元计数问题 无向三元计数问题 根号分治 记 d i : i d_i:i di​:i 在原图中的度数。 按照以下规则改写无向...
  • 我们不妨先做一些这个随机的有向无环图的假设: 首先,它是个有向无环图,并且没有重边 假设随机从图中取出两个不相同的点,那么它们之间有边的概率为固定值(其实还可以有其他类型的随机) 我们一个一个来解决...
  • 设想: 要找一个图中是否有经过某一点的,我们可以从这一点进行深度遍历,某一点的深度遍历的执行过程为:每次选取此顶点的一个邻接点向下遍历,直到某一点的邻接点全部处理完后返回到上一个顶点,处理上一个顶点...
  • 在实现,每当我们处理节点时,我们首先检查是否有任何子节点也是间接后代.如果是,请删除边缘.如果没有,请保留.当处理所有子项时,我们通过将其所有后代添加到父项的间接后代集来更新其父项的信息.如果处理了父项的...
  • 有向无环图 没有,有方向的(directed acycline graph),简称 DAG 有向树、有向无环图和有向的对比图例 有向无环图是描述含有公共子式的表达式...检查一个有向是否存在环比检查一个无向是否存在..
  • 对一个有向无环图(Directed Acyclic Graph简称DAG)G进行拓扑排序,是将G所有顶点排成一个线性序列,使得图中任意一对顶点u和v,若边(u,v)∈E(G),则u在线性序列出现在v之前。通常,这样的线性序列称为满足拓扑...
  •  令牌网是一种以环形网络拓扑结构为基础发展起来的局域网,如1-12所示。虽然它在物理组成上也可以是星型结构连接,但在逻辑上仍然以的方式进行工作。其通信传输介质可以是无屏蔽双绞线、屏蔽双绞线和光纤等。...
  • 即:原图中(u,v),(v,w),(u,w)(u,v),(v,w),(u,w)(u,v),(v,w),(u,w)(不妨设u优先级比v高,v优先级比w高)在新图上表现为(u−>v,v−>w,u−>w)(u->v,v->w,u->w)(u−>v,v−>w,u−>w) 手推...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 73,104
精华内容 29,241
关键字:

检查图中的环