Java实现 洛谷 P3916 图的遍历（反向DFS+记忆化搜索）

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 );

		}

	}

}