題目描述

河南省實驗中學(xué)的一名教師T的一封辭職信引發(fā)熱評，辭職的理由僅有10個字：“世界那么大，我想去看看”。網(wǎng)友評這是“史上最具情懷的辭職信，沒有之一”。經(jīng)采訪得知，作者為2004年7月入職河南省實驗中學(xué)的一名女心理教師，已經(jīng)任職11年之久。如此任性的辭職信，領(lǐng)導(dǎo)最后還真批準了。?


現(xiàn)在假設(shè)世界上有n個城市（用1~n標識 ），有m個高鐵線路ei 格式為 xi yi ;? ?T的開始城市 f, 結(jié)束城市 e，她希望把所有的道路 都不重復(fù)的訪問一遍，如果可以做到就輸出YES?否則輸出 NO

輸入

城市數(shù)n和鐵路m??
開始城市 f 和目的城市e?
每條鐵路的起止城市 xi? yi???

輸出

如果可以從開始城市 f,結(jié)束城市 e ，并把所有路徑都不重復(fù)的訪問一遍，就輸出YES 否則輸出NO

樣例輸入

3 2 1 3 1 2 2 3

樣例輸出

YES

提示

路線沒有方向性，但是兩個城市之間可能有多個線路 數(shù)據(jù)保證圖一定是聯(lián)通的

import java.util.*; public class Main {static int n;static int m;static Set<Integer> set1;static Scanner cin=new Scanner(System.in);public static void main(String[] args) {n=cin.nextInt();m=cin.nextInt();int f=cin.nextInt();int e=cin.nextInt();Graph G=new Graph();List<Integer> list1=new LinkedList<>();List<Integer> list2=new LinkedList<>();Paths search=new Paths(G,f);if (search.hasPathTo(e)) {for (int x : search.pathTo(e)) {list1.add(x);}}Collections.sort(list1);for(int i:set1){list2.add(i);}if(list1.equals(list2)){System.out.println("YES");}else{System.out.println("NO");}cin.close();}private static class Graph {static int V;int E;static LinkedList<Integer>[] adj;public Graph() {this.V=n;this.E=m;adj=new LinkedList[V+1];for(int v=1;v<V+1;v++){adj[v]=new LinkedList<>();}set1=new HashSet<>();for(int i=0;i<E;i++){int v=cin.nextInt();int w=cin.nextInt();set1.add(v);set1.add(w);addEdge(v,w);}}private void addEdge(int v, int w) {adj[v].add(w);adj[w].add(v);}public Iterable<Integer> adj(int v){return adj[v];}public int V(){return V;}}private static class Paths {private boolean[] marked;private int[] edgeto;private final int s;public Paths(Graph G, int f) {marked=new boolean[G.V()+1];edgeto=new int[G.V()+1];this.s = f;dfs(G,s);}private void dfs(Graph G, int v) {marked[v]=true;for(int w:G.adj(v)){if(!marked[w]){edgeto[w]=v;dfs(G,w);}}}public boolean hasPathTo(int v){return marked[v];}public Iterable<Integer> pathTo(int v){if(!hasPathTo(v)) return null;Stack<Integer> path=new Stack<>();for(int x=v;x!=s;x=edgeto[x])path.push(x);path.push(s);return path;}} }

總結(jié)

以上是生活随笔為你收集整理的问题 C: 世界那么大，我想去看看的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。