1267 - Network【狂dfs、模拟】

各种dfs

按照LRJ书上的思路写就行了

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<map>
#include<stack>
#include<set>
#include<queue>
#include<vector>
using namespace std;
const int maxn = 1111;
vector<int>G[maxn];
set<int>is_node;
int n,s,k;
int fa[maxn];
int vis[maxn];
int have[maxn];
struct Node{
    int id;
    int dep;
    Node(int i = 0,int d = 0):id(i),dep(d){};
    friend bool operator < (Node a,Node b){
        return a.dep > b.dep;
    }
};
vector<Node>node;
void dfs_node(int u,int dep,int f){
    int le = 0;
    vis[u] = 1;
    fa[u] = f;
    for(int i = 0; i < G[u].size(); i++){
        int v = G[u][i];
        if(!vis[v]){
            dfs_node(v,dep + 1,u);
            le = 1;
        }
    }
    if(!le){
        node.push_back(Node(u,dep));
        is_node.insert(u);
    }
    return;
}
void debug(){
    for(int i = 0; i < node.size(); i++)
        printf("%d %d\n",node[i].id,node[i].dep);
}
void dfs_solve(int u,int d){
    if(d == k)
        return;
    for(int i = 0; i < G[u].size(); i++){
        int v = G[u][i];
        if(!vis[v]){
            if(is_node.count(v))
                have[v] = 1;
            else
                dfs_solve(v,d + 1);
        }
    }
    return;
}
int judge(){
    int e = 0;
    for(int i = 0; i < node.size(); i++)
        if(!have[node[i].id]){
            e = node[i].id;
            break;
        }
    if(!e) return 0;
    int d = 0;
    while(fa[e] != -1 && d < k){
        e = fa[e];
        d ++;
    }
    return e;
}
int main(){
    int T;
    scanf("%d",&T);
    while(T--){
        scanf("%d%d%d",&n,&s,&k);
        for(int i = 1; i <= n; i++) G[i].clear();
        node.clear();
        is_node.clear();
        memset(vis,0,sizeof(vis));
        memset(have,0,sizeof(have));
        for(int i = 0; i < n - 1; i++){
            int a,b;
            scanf("%d%d",&a,&b);
            G[a].push_back(b);
            G[b].push_back(a);
        }
        dfs_node(s,0,-1);
        sort(node.begin(),node.end());
        int serve = s;
        int ans = 0;
        do{
            memset(vis,0,sizeof(vis));
            dfs_solve(s,0);
            s = judge();
            if(!s) break;
            ans ++;
        }while(true);
        printf("%d\n",ans);
    }
    return 0;
}