首页 > 其他分享 >P3916 图的遍历——反图

P3916 图的遍历——反图

时间:2023-01-31 20:13:29浏览次数:40  
标签:遍历 int d% dfs P3916 ans 反图

给出 \(N\) 个点,\(M\) 条边的有向图,对于每个点 \(v\),求 \(A(v)\) 表示从点 \(v\) 出发,能到达的编号最大的点。

这题有一个巧妙思路,构造反图,把依次找每个能到达的最大的点,转化为从大到小枚举每个点搜索当前点能到达的所有点,第一次找到的点一定是最大点。

反图思路就是建每一条有向边的反向边。这种思想很重要

#include <bits/stdc++.h>

using namespace std;

const int N = 100005;
int n, m;
vector<int>e[N];
int ans[N];
int f;
void dfs(int u)
{
	if (ans[u]) {
		return;
	}
	ans[u] = f;
	for (int v : e[u]) {
		dfs(v);
	}
}

int main()
{
	scanf("%d%d", &n, &m);
	for (int i = 0, a, b; i < m; i++) {
		scanf("%d%d", &a, &b);
		// opposite edge
		e[b].push_back(a);
	}
	for (int i = n; i >= 1; i--) {
		if (!ans[i]) {
			f = i;
			dfs(i);
		}
	}
	for (int i = 1; i <= n; i++) {
		printf("%d ", ans[i]);
	}
	printf("\n");
	return 0;
}

标签:遍历,int,d%,dfs,P3916,ans,反图
From: https://www.cnblogs.com/CYLSY/p/17080330.html

相关文章

  • php in_array 遍历,in_array大数组查询性能问题
    问题最近在实现一个项目接口的时候发现当数组过大的时候,数据返回的速度有点慢。接口数据返回最长反应时间2s,经过反复调试发现代码段耗时最长的部分在in_array()函数。解决......
  • 图的遍历
    n=0N=10000all=0go=[0]*Nhd=[0]*Nnxt=[0]*Ndefadd_(x,y):globalallall+=1nxt[all]=hd[int(x)]go[all]=yhd[x]=alldefdfs(x):p......
  • Redis 遍历指定格式的所有key
        Redis作为当前最流行的内存型NoSQL数据库,被许多公司所使用,我们在实际使用中一般都会为key带上指定的前缀或者其他定义的格式,那么我们怎样能取出符合条件......
  • BM25 二叉树的后序遍历
    https://www.nowcoder.com/practice/1291064f4d5d4bdeaefbf0dd47d78541?tpId=295&tqId=2291301&ru=/exam/oj&qru=/ta/format-top101/question-ranking&sourceUrl=%2Fexam%2......
  • BM24 二叉树的中序遍历
    https://www.nowcoder.com/practice/0bf071c135e64ee2a027783b80bf781d?tpId=295&tqId=1512964&ru=/exam/oj&qru=/ta/format-top101/question-ranking&sourceUrl=%2Fexam%......
  • [数据结构]二叉树的前中后序遍历(递归+迭代实现)
    二叉树的遍历主要的三种遍历方式二叉树主要的遍历方式有前序遍历、中序遍历和后序遍历。(1)前序遍历:根节点-->左子树-->右子树(2)中序遍历:左子树-->根节点-->右子树(3)后序......
  • 双向链表 添加与遍历
    packagecom.pay.test;//定义节点publicclassDoubleLinkedList{//初始化头节点privateHeroNodehead=newHeroNode(0,"","");//返回节点头p......
  • 二叉树遍历 前序 中序 后序
    packagecom.pay.test;importjava.util.LinkedList;publicclassNode{privateIntegerdata;privateNodeleft;privateNoderight;publ......
  • 遍历树节点
    exportconstforeachTree=(data,callback,childrenName='children')=>{for(leti=0;i<data.length;i++){callback(data[i])if(data[i][ch......
  • 代码随想录算法训练营第15天 | 二叉树的层序遍历226. 翻转二叉树 101.对称二叉树
    102.二叉树的层序遍历文章:代码随想录(programmercarl.com)视频:讲透二叉树的层序遍历|广度优先搜索|LeetCode:102.二叉树的层序遍历_哔哩哔哩_bilibili思路:层序遍......