【PTA-训练day27】L2-038 病毒溯源 + L2-039 清点代码库 + L2-040 哲哲打游戏

目录

L2-038 病毒溯源 - dfs求树最大深度及路径

L2-039 清点代码库 - STL嵌套使用+结构体自定义排序

L2-040 哲哲打游戏 - vector建图

---

L2-038 病毒溯源 - dfs求树最大深度及路径

PTA | 程序设计类实验辅助教学平台

思路：

• 用链表建树 找到根节点
• dfs根节点寻找最大深度
• son[u]存u的子节点
• 如果深度比当前深度大，则更新深度和路径
• 如果深度=当前深度，则路径取节点值小的

#include <bits/stdc++.h>
using namespace std;const int N=10010,M=N*2;
int h[N],ne[M],e[M],idx;
int st[N],son[N];void add(int a,int b)
{e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}int dfs(int u) //搜索u结点到叶节点的最长路径值
{int res=0;son[u]=-1;for(int i=h[u];i!=-1;i=ne[i]){int j=e[i];int d=dfs(j);if(res<d) res=d,son[u]=j;else if(res==d) son[u]=min(son[u],j);}return res+1;
}int main()
{int n;cin>>n;memset(h,-1,sizeof h);for(int i=0;i<n;i++){int cnt;cin>>cnt;while(cnt--){int x;cin>>x;add(i,x);st[x]=true; //把有父节点的点都标记 则未标记的就是根节点}}int rt=0;while(st[rt]) rt++; //找根节点cout<<dfs(rt)<<endl;cout<<rt;while(son[rt]!=-1){rt=son[rt];cout<<" "<<rt;}
}

L2-039 清点代码库 - STL嵌套使用+结构体自定义排序

PTA | 程序设计类实验辅助教学平台

#include <bits/stdc++.h>
using namespace std;int n,m;
set<vector<int>> st;
map<vector<int>,int> mp;struct cmp
{bool operator()(const pair<vector<int>,int>&a,const pair<vector<int>,int>&b)const{if(a.second!=b.second) return a.second>b.second;else return a.first<b.first;}
};int main()
{cin>>n>>m;while(n--){vector<int> v;for(int i=0;i<m;i++){int x; cin>>x;v.push_back(x);}st.insert(v);mp[v]++;}cout<<st.size()<<endl;set<pair<vector<int>,int>,cmp> s;for(auto x:st) s.insert({x,mp[x]});for(auto x:s){cout<<x.second;for(int i=0;i<x.first.size();i++) cout<<" "<<x.first[i];cout<<endl;}}

L2-040 哲哲打游戏 - vector建图

PTA | 程序设计类实验辅助教学平台

#include <bits/stdc++.h>
using namespace std;const int N=1e5+10;
vector<int> v[N];
int save[N];int main()
{int n,m;cin>>n>>m;for(int i=1;i<=n;i++){int k;cin>>k;for(int j=0;j<k;j++){int x;cin>>x;v[i].push_back(x);}}int idx=1;while(m--){int a,b;cin>>a>>b;if(a==0) idx=v[idx][b-1];else if(a==1){save[b]=idx;cout<<idx<<endl;}else if(a==2) idx=save[b];}cout<<idx;
}