算了下复杂度好像是n^3 就感觉不大好做。结果n^31a。。。
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <string.h>
#include <map>
#include <vector>
#include <string>
#include <queue>
using namespace std;
#define eps 1e-9
#define PI acos(-1.0)
#define N 1005
#define inf 10000000
map<string,int>mp;
vector<int>G[N*2];
vector<string>ans;
int Stack[N*2],topans;
int n, m;
char s[N*2][20], tmp[2][20];
int vis[N*2];
bool bfs(int u){
memset(vis,0,sizeof vis);
vis[u] = -1;
queue<int>q;
for(int i = 0; i < G[u].size(); i++)q.push(G[u][i]),vis[G[u][i]]=-1;
int siz = -2;
while(!q.empty()){
u = q.front(); q.pop();
for(int i = 0; i < G[u].size(); i++){
int v = G[u][i]; if(vis[v]==-1)continue;
vis[v]++;
if(siz<vis[v]){siz = vis[v];topans = 1;Stack[0] = v;}
else if(siz==vis[v]){Stack[topans++] = v;}
}
}
if(siz<0)return false;
ans.clear();
for(int i = 0; i < topans; i++)ans.push_back(s[Stack[i]]);
sort(ans.begin(), ans.end());
for(int i = 0; i < ans.size();i++){cout << ans[i];i==ans.size()-1?puts(""):printf(" ");}
return true;
}
int main()
{
int T, Cas = 1, i, j; scanf("%d",&T);
while(T--){
mp.clear();
scanf("%d %d",&n,&m);
for(i = 1; i <= 2*n; i++)G[i].clear();
int top = 0;
while(n--)
{
scanf("%s %s",tmp[0],tmp[1]);
if(mp.find(tmp[0])==mp.end()){
mp[tmp[0]] = ++top;
memcpy(s[top],tmp[0],sizeof tmp[0]);
i = top;
}
else i = mp.find(tmp[0])->second;
if(mp.find(tmp[1])==mp.end()){
mp[tmp[1]] = ++top;
memcpy(s[top],tmp[1],sizeof tmp[1]);
j = top;
}
else j = mp.find(tmp[1])->second;
G[i].push_back(j);G[j].push_back(i);
}
printf("Case %d:\n",Cas++);
while(m--)
{
scanf("%s",tmp[0]);
i = mp.find(tmp[0])->second;
if(bfs(i)==false)puts("-");
}
}
return 0;
}