題目描述

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.

?

樣例輸入

復制樣例數據

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.

?

題目大意：

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

解題思路：

我們可以根據m行說服關系建一個有向圖（樹），不難發現，若以u中的一個人為根節點，那么他肯定能說服在以他為根的路徑上的所有在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;
}

?