Java实现 洛谷 P3916 图的遍历（反向DFS+记忆化搜索）
2024-08-25 15:19:00
P3916 图的遍历
输入输出样例
输入
4 3
1 2
2 4
4 3
输出
4 4 3 4
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.StreamTokenizer;
import java.util.Vector;
public class 图的遍历 {
static Vector<Vector<Integer>> vec = new Vector<Vector<Integer>>();
static int[] num;
public static void main(String[] args) throws IOException {
StreamTokenizer st = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
st.nextToken();
int V = (int) st.nval;
st.nextToken();
int E = (int) st.nval;
for (int i = 0; i <= V; i ++) {
vec.add(new Vector<Integer>());
}
int head,tail;
for(int i=0;i<E;i++)
{
st.nextToken();
head = (int) st.nval;
st.nextToken();
tail = (int) st.nval;
vec.get(tail).add(head);
}
num = new int[V + 1];
for (int i = V; i >=1; i--) {
dfs(i,i);
}
for (int i = 1; i<=V; i++) {
System.out.print(num[i]+" ");
}
}
public static void dfs(int start,int end) {
if(num[start]!=0) {
return ;
}
num[start]=end;
int res = 0;
for (int node : vec.get(start)) {
dfs(node,end );
}
}
}
最新文章
- linux bash 笔记
- 关于Listview布局的一点经验
- win2008远程桌面会话数增加
- Json.Net Demo2
- excel中单元格计算
- cursorfilter
- Unity学习笔记（一）——基本概念之场景（Scene）
- Java基础知识强化26：Object类之hashCode()方法、getClass()方法
- gulp压缩js
- javascript技术难点之this、new、apply和call详解
- android app开发
- 浅谈JavaScript的面向对象程序设计（四）
- 浅析构造函数，及public、private、protected、final、this、super关键字
- Xamarin Essentials教程语音播报TextToSpeech
- ROS教程1 消息查看和使用服务
- AngualrJS中每次$http请求时的一个遮罩层Directive
- 入手Docker容器注意事项：命令结束容器退出
- 2018.08.31 bzoj1419 Red is good（期望dp）
- jenkins multijob 插件使用
- windows下python安装Numpy和Scipy模块