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

小鱼儿 2023-07-22 06:58 3阅读 0赞

## P3916 图的遍历 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ExNDM5Nzc1NTIw_size_16_color_FFFFFF_t_70]

输入输出样例
    输入  
    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 );
    		} 
    	}
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ExNDM5Nzc1NTIw_size_16_color_FFFFFF_t_70]: /images/20230528/9f0f778b0edd4a7f951020e126fb3f34.png