程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> 關於C++ >> NYOJ20 吝啬的國度 (dfs)

NYOJ20 吝啬的國度 (dfs)

編輯:關於C++

題目描述:

 

在一個吝啬的國度裡有N個城市,這N個城市間只有N-1條路把這個N個城市連接起來。現在,Tom在第S號城市,他有張該國地圖,他想知道如果自己要去參觀第T號城市,必須經過的前一個城市是幾號城市(假設你不走重復的路)。
輸入第一行輸入一個整數M表示測試數據共有M(1<=M<=5)組
每組測試數據的第一行輸入一個正整數N(1<=N<=100000)和一個正整數S(1<=S<=100000),N表示城市的總個數,S表示參觀者所在城市的編號
隨後的N-1行,每行有兩個正整數a,b(1<=a,b<=N),表示第a號城市和第b號城市之間有一條路連通。輸出每組測試數據輸N個正整數,其中,第i個數表示從S走到i號城市,必須要經過的上一個城市的編號。(其中i=S時,請輸出-1)樣例輸入
1
10 1
1 9
1 8
8 10
10 3
8 6
1 2
10 4
9 5
3 7
樣例輸出
-1 1 10 10 9 8 3 1 1 8

題目分析:

不要一位此題只是簡單的單聯通問題,此題是個深度搜索問題,正常的搜索問題,可能是題目沒有描述清楚,本題代碼參考的大神的代碼。。。

AC代碼:

 

 
/**
 *dfs,深度搜索,
 *注意找到最好的路線,從A能到b,那麼從b必然也能到a
 */
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
int map_vis[100005];
void a_prior_dfs(int a){
    int p=map_vis[a];
    if(p!=0){//繼續向前搜素
        a_prior_dfs(p);
        map_vis[p]=a;//反向標記
    }
}

int main()
{
	int t,n,s;
	scanf(%d,&t);
	while(t--){
        memset(map_vis,0,sizeof(map_vis));
        scanf(%d%d,&n,&s);
        int a,b;
        for(int i=0;i

 

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved