首页 > 代码库 > hiho1041 - 树，遍历

hiho1041 - 树，遍历

2024-10-31 03:33:03   206人阅读

题目链接

给一棵树，给一个序列，问能不能按这个序列遍历这棵树，满足每条边最多经过两次。

--------------------------------------------------------------------------

因为数据小，所以直接用二维数组存储边，同时用这个数组记录边的访问次数。

因为是树，任意两个顶点间的路径只有一条，所以问题简单了很多

依次处理给定的序列，从一个顶点dfs到另一个顶点的同时检查该路径上的边是否访问超过两次了，如果超过两次则返回false

 

#include <set>
#include <map>
#include <stack>
#include <queue>
#include <cmath>
#include <vector>
#include <string>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>

#define MAX(a,b) ((a)>=(b)?(a):(b))
#define MIN(a,b) ((a)<=(b)?(a):(b))
#define OO 0x0fffffff
using namespace std;
typedef long long LL;


const int N = 128;
int maze[N][N];
bool vis[N];
int n,m;
bool dfs(int s,int e){
    vis[s] = true;
    for(int i=1;i<=n;i++){
        if(maze[s][i]&&(!vis[i])){
            if(i==e||dfs(i,e)) {
              if(maze[s][i]>=3) return false;
              maze[s][i]++;
              maze[i][s]++;
              return true;
            }
        }
    }
    return false;
}
int main(){
    int t;
    int a,b,c;
    int epos,spos;
    for(scanf("%d",&t);t--;){
        scanf("%d",&n);
        memset(maze,0,sizeof(maze));
        for(int i=1;i<n;i++){
            scanf("%d%d",&a,&b);
            maze[a][b] = maze[b][a] = 1;
        }
        cin>>m;
        epos = 1;
        bool flag = true;
        while(m--){
            spos = epos;
            scanf("%d",&epos);
            if(flag){
                memset(vis,false,sizeof(vis));
                flag = dfs(spos,epos);
            }
        }
        if(flag) puts("YES");
        else puts("NO");
    }
    return 0;
}

 

hiho1041 - 树，遍历


联系
我们