題目描述

Dylan is a corrupt politician trying to steal an election. He has already used a mind-control technique to?enslave some set U of government representatives. However, the representatives who will be choosing the?winner of the election is a di?erent set V . Dylan is hoping that he does not need to use his mind-control device?again, so he is wondering which representatives from V can be convinced to vote for him by representatives?from U.
Luckily, representatives can be persuasive people. You have a list of pairs (A, B) of represenatives, which?indicate that A can convice B to vote for Dylan. These can work in chains; for instance, if Dylan has?mind-controlled A, A can convince B, and B can convince C, then A can e?ectively convince C as well.

?

輸入

The first line contains a single integer T (1 ≤ T ≤ 10), the number of test cases. The first line of each test?case contains three space-separated integers, u, v, and m (1 ≤ u, v, m ≤ 10,000). The second line contains a?space-separated list of the u names of representatives in U. The third line contains a space-separated list of?the v names of representatives from V . Each of the next m lines contains a pair of the form A B, where A?and B are names of two representatives such that A can convince B to vote for Dylan. Names are strings of?length between 1 and 10 that only consists of lowercase letters (a to z).

?

輸出

For each test case, output a space-separated list of the names of representatives from T who can be convinced?to vote for Dylan via a chain from S, in alphabetical order.

?

樣例輸入

復(fù)制樣例數(shù)據(jù)

2 1 1 1 alice bob alice bob 5 5 5 adam bob joe jill peter rob peter nicole eve saul harry ron eve adam joe chris jill jack jack saul

樣例輸出

bob peter saul

?

提示

In the second test case, Jill can convince Saul via Jack, and Peter was already mind-controlled.

?

題目大意：

先是輸入樣例的組數(shù)，對于每組樣例，先輸入三個(gè)整數(shù)u,v,m，下面一行輸入u個(gè)名稱，其下一行輸入v個(gè)名稱，然后是m組說服關(guān)系，每行輸入兩個(gè)名稱s1,s2，若u中的一個(gè)人能夠說服v中的人投票給Dylan，則將v中此人記錄下來，最后將答案按照字典序輸出，同時(shí)有一點(diǎn)需注意，若假如某人即在u中又在v中，則他肯定能說服自己。

解題思路：

我們可以根據(jù)m行說服關(guān)系建一個(gè)有向圖（樹），不難發(fā)現(xiàn)，若以u中的一個(gè)人為根節(jié)點(diǎn)，那么他肯定能說服在以他為根的路徑上的所有在v中的人都能被他說服投票給Dylan，所以可以通過dfs尋找這樣的人，把人名存入set中，最后輸出即可。

代碼：

#include <cstdio> #include <iostream> #include <algorithm> #include <cmath> #include <cstdlib> #include <cstring> #include <map> #include <stack> #include <queue> #include <vector> #include <bitset> #include <set> #include <utility> #include <sstream> #include <iomanip> using namespace std; typedef long long ll; typedef unsigned long long ull; #define inf 0x3f3f3f3f #define rep(i,l,r) for(int i=l;i<=r;i++) #define lep(i,l,r) for(int i=l;i>=r;i--) #define ms(arr) memset(arr,0,sizeof(arr)) //priority_queue<int,vector<int> ,greater<int> >q; const int maxn = (int)1e5 + 5; const ll mod = 1e9+7; map<string,int> m; bool vis[200100]; set<string> ss; vector<int> mapp[400100]; map<int,string> str; int l,r; void dfs(int x) {if(mapp[x].size()==0) return;for(int i=0;i<mapp[x].size();i++) {if(vis[mapp[x][i]]==false) { /* cout<<str[x]<<" "<<str[mapp[x][i]]<<endl; */ vis[mapp[x][i]]=true;if(mapp[x][i]>=l&&mapp[x][i]<=r) ss.insert(str[mapp[x][i]]);dfs(mapp[x][i]);}}} int main() {#ifndef ONLINE_JUDGEfreopen("in.txt", "r", stdin);#endif//freopen("out.txt", "w", stdout);ios::sync_with_stdio(0),cin.tie(0);int t;cin>>t;while(t--) {int u,v,mm;rep(i,1,40000) mapp[i].clear();string s;m.clear();memset(vis,false,sizeof vis);ss.clear();int cnt=0;cin>>u>>v>>mm;rep(i,1,u) {cin>>s;cnt++;m[s]=cnt;str[cnt]=s;}l=cnt+1;rep(i,1,v) {cin>>s;if(m[s]!=0) {ss.insert(s);}else {cnt++;m[s]=cnt;str[cnt]=s;}}r=cnt;string s1,s2;rep(i,1,mm) {cin>>s1>>s2;if(m[s1]==0) {cnt++;m[s1]=cnt;str[cnt]=s1;}if(m[s2]==0) {cnt++;m[s2]=cnt;str[cnt]=s2;}mapp[m[s1]].push_back(m[s2]);}rep(i,1,u) {if(vis[i]==false) {vis[i]=true;dfs(i);}}set<string>::iterator it1;for(it1=ss.begin();it1!=ss.end();it1++) cout<<*it1<<" ";cout<<endl;}return 0; }

?

總結(jié)

以上是生活随笔為你收集整理的【dfs】Election of Evil的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。