首页 > 其他分享 >图的遍历

图的遍历

时间:2024-02-03 16:33:06浏览次数:32  
标签:遍历 idx int ne st limit 号点

/*
反向考虑,反向建图,考虑从x号点出发,可以到达哪些点,我们从n~1开始枚举
如果某一个点被更新到,呢么这个点一定不会被后面的点更新,就直接可以标记掉,从n号点出发可以到达5号点,呢么从n-1号点出发就
可以直接跳过5号点,还有5号点能到达的点。
 复杂度是O(n),这样的想法很常见
 */
#include <bits/stdc++.h>
#define CLOSE ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
const int N = 1e5 + 10, M = N, mod = 1e9 + 7;
using namespace std;
int h[N], e[M], ne[M], idx = 0;
int n, m, ans[N];
bool st[N];
void add(int x, int y){
    e[idx] = y, ne[idx] = h[x], h[x] = idx ++;
}
void dfs(int x, int limit){
    if(st[x]) return;
    st[x] = true;
    ans[x] = limit;
    for(int i = h[x]; ~ i; i = ne[i]){
        int j = e[i];
        dfs(j, limit);
    }
}
int main()
{
    CLOSE;
    memset(h, -1, sizeof h);
    cin >> n >> m;
    for(int i = 1; i <= m; i ++){
        int x, y;
        cin >> x >> y;
        add(y, x);
    }
    for(int i = n; i >= 1; i --){
        if(!st[i]){
            dfs(i, i);
        }
    }
    for(int i = 1; i <= n; i ++){
        cout << ans[i] << " ";
    }
    return 0;
}

标签:遍历,idx,int,ne,st,limit,号点
From: https://www.cnblogs.com/acwhr/p/18004900

相关文章

  • 二叉树的广度遍历/层序遍历
    privateInteger[]breadthSearch(TreeNoderoot){ List<Integer>list=newArrayList<Integer>();//存放节点值 ArrayDeque<TreeNode>queue=newArrayDeque<TreeNode>();//队列,用来存放节点 queue.add(root); while(!queue.isEmpty()){ TreeNo......
  • JS遍历对象的方法 Object.keys() Object.values()
    1.Object.keys():返回对象可枚举属性组成的数据2.Object.values():返回对象可枚举的属性的属性值,组成的数据letperson={name:'小李',age:'15',}console.log(Object.keys(person));//['name','age']//返回对象可枚举属性组成的数......
  • [刷题笔记] ybt 1364:二叉树遍历(flist)
    Problem_LinkDescription树和二叉树基本上都有先序、中序、后序、按层遍历等遍历顺序,给定中序和其它一种遍历的序列就可以确定一棵二叉树的结构。假定一棵二叉树一个结点用一个字符描述,现在给出中序和按层遍历的字符串,求该树的先序遍历字符串。Analysis我们先前做过给定前序......
  • Java中,遍历List集合有以下四种方式
    1.增强for循环(foreach):这种方式是最简单的,也是最易读的。它直接对集合中的每个元素进行操作,不需要额外的迭代器或索引变量。但是,这种方式不能在遍历过程中修改集合的结构(例如添加或删除元素)。2.使用迭代器:迭代器提供了一种通用的遍历集合的方式,可以在遍历过程中修改集合的结构。但......
  • 遍历转树结构
    遍历转树结构{varlist=newList<Foo>{newFoo("111",1),newFoo("112",2),newFoo("113",2),newFoo("114",2),newFoo("115",3),newFoo("116",1),newFoo("......
  • SqlServer中使用游标遍历数据集合
    具体代码如下所示:/***************************************** 实例:打印输出数据表BUS_Test中的Name和Age字段的值*****************************************/--声明遍历@Name和@AgeDECLARE@NameNVARCHAR(50),@AgeINT--声明游标C_UserDECLAREC_UserCURSORFAST_FOR......
  • 图的表示与遍历
    讲解           代码 P5318【深基18.例3】查找文献 #include<bits/stdc++.h>usingnamespacestd;constintN=100010;vector<int>a[N];intn,m,x,y,vis[N];queue<int>q;voiddfs(ints){ if(vis[s]==1)return; vis[s]=......
  • golang 遍历目录的两种方式、删除目录的两种方式
    funcmain(){ directory:="/Users/mike/Downloads" //不会递归只会读取当前的单层目录 directories,err:=os.ReadDir(directory) iferr!=nil{ fmt.Println(err) } for_,d:=rangedirectories{ fmt.Println(d.Name(),d.IsDir()) } //会递归遍历所......
  • 树的遍历
    二叉树的遍历前序遍历#include<bits/stdc++.h>usingnamespacestd;intn;structs{ intl,r,d;}a[10005];voidf(intt)//前序{ if(t==0)return; cout<<t<<''; f(a[t].l); f(a[t].r);}intmain(){cin>>n;for(inti=1;i<......
  • KY11 二叉树遍历C++
    这个题目思路其实就是先序遍历的变形。相当于沿着先序遍历的顺序跟着构建二叉树就行。然后中序遍历这个树。#include<iostream>#include<string>usingnamespacestd;structtnode{chardata;structtnode*left;structtnode*right;};typedefstructt......