dfs+鄰接表儲存或者哈希表的運用，考察我們對數據的存儲

?

?

本題核心就是在求從根節點開始的兩棵樹相同的最長序列，首先確定用dfs進行深搜，對于節點的形式可以用鄰接表，鄰接矩陣，哈希表來進行存儲數據。下面看代碼

?鄰接表

#include <bits/stdc++.h>
using namespace std;
int n,m;
int mp[200005];
int np[200005];
vector<int> v1[200005];
vector<int> v2[200005];
int cont;//記錄最長的相同序列
void dfs(int x,int y,int sum)
{if(np[x]!=mp[y]) return;//如果序列開始不同直接returncont=max(cont,sum+1);//開始遍歷相鄰的節點for(auto& i:v1[x]){for(auto& j:v2[y]){dfs(i,j,sum+1);}}
}
int main()
{cin>>n>>m;for(int i=0;i<n;i++){cin>>np[i];}for(int j=0;j<m;j++){cin>>mp[j];}int l,r;for(int i=0;i<n-1;i++){cin>>l>>r;v1[l].push_back(r);}for(int i=0;i<m-1;i++){cin>>l>>r;//鄰接表儲存v2[l].push_back(r);}dfs(1,1,0);cout<<cont;return 0;
}

map?

#include <bits/stdc++.h>
#define N 200005
using namespace std;
map<int,vector<int>> m1,m2;
int n,m,a[N],b[N],ans,u,v;
void dfs(int x,int y,int count)
{if(a[x]!=b[y])return;ans=max(ans,count+1);//記錄最長相同序列長度for(int i=0;i<m1[x].size();i++){for(int j=0;j<m2[y].size();j++){int a1=m1[x][i];int b1=m2[y][j];}dfs(a1,b1,count+1);//搜索所有相鄰節點}
}
int main()
{cin>>n>>m;for(int i=1;i<=n;i++)cin>>a[i];for(int i=1;i<=m;i++)cin>>b[i];for(int i=1;i<=n-1;i++){cin>>u>>v;m1[u].push_back(v);}for(int i=1;i<=m-1;i++){cin>>u>>v;m2[u].push_back(v);}dfs(1,1,0);
cout<<ans;
}