題意：給出名字和地方，地方會重定向，最后再給出名字，問現在屬于哪里？

用并查集。

//#pragma comment(linker,"/STACK:1024000000,1024000000") #include<iostream> #include<cstdio> #include<string> #include<cstring> #include<vector> #include<cmath> #include<queue> #include<stack> #include<map> #include<set> #include<algorithm> #include <stack> using namespace std; typedef long long lon; const lon SZ=100010,INF=0x7FFFFFFF; map<string,string> mp; vector<string> ls; int arr[SZ];void init() {for(int i=0;i<SZ;++i)arr[i]=i; }int find(int x) {return arr[x]==x?x:arr[x]=find(arr[x]); }void adj(int x,int y) {int rtx=find(x),rty=find(y);arr[rtx]=rty; }void work() {mp.clear(),ls.clear();int n;cin>>n;for(int i=0;i<n;++i){string name,bel;cin>>name>>bel;mp[name]=bel;ls.push_back(bel);}sort(ls.begin(),ls.end());ls.erase(unique(ls.begin(),ls.end()),ls.end());int m;cin>>m;init();for(int i=0;i<m;++i){string src,dst;cin>>src>>dst;int a=lower_bound(ls.begin(),ls.end(),src)-ls.begin();int b=lower_bound(ls.begin(),ls.end(),dst)-ls.begin();adj(a,b);}int qnum;cin>>qnum;for(int i=0;i<qnum;++i){string str;cin>>str;string src=mp[str];int id=lower_bound(ls.begin(),ls.end(),src)-ls.begin();id=find(id);cout<<str<<" "<<ls[id]<<endl;} }int main() {std::ios::sync_with_stdio(0);//freopen("d:\\1.txt","w",stdout); lon casenum;cin>>casenum;for(lon time=1;time<=casenum;++time)//for(;scanf("%d",&n)!=EOF;) {work();}return 0; }

?

轉載于:https://www.cnblogs.com/gaudar/p/9751554.html

總結

以上是生活随笔為你收集整理的spoj Help the Military Recruitment Office!的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。