HDU 4039 The Social Network bfs

算了下复杂度好像是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;
}

HDU 4039 The Social Network bfs,布布扣,bubuko.com

HDU 4039 The Social Network bfs

原文：http://blog.csdn.net/acmmmm/article/details/25790405