[数据结构与算法]hdu4460题解与思考（没解出来别看）

hdu4460 题解与思考 Friend Chains

1. 题意：
   简单来说就是自己任意输入一个图的结点和边，找到一个最小路径长度k，任意两点的连通路径长度都小于等于，如果有孤立点，则输出-1

2. 思路:
   首先能够想到用bfs做遍历，由于起点不固定，所以需要for循环对每个点做遍历，比较可以得到k。至于图的构建，可以考虑用邻接矩阵，这样vis也可以用二维数组。本题有一个问题，输入的名字并不直接对应数字，这就给我们在邻接矩阵上直接处理边的关系带来了麻烦，解决方案是使用map库，map的好处是可以直接通过关键字访问对应的id，且复杂度较低（O(log2n)）。注意如果图中有孤立点，就没有点能与之联系，视为距离无限，输出-1。
   结合上面的思路可以较快的得到下面的代码：

#include<iostream>
#include<queue>
#include<string>
#include<map>
using namespace std;

struct node {
	int num;
	int step;
};
int edge[1000][1000] = {0};//用来记录边的连接情况
bool vis[1000][1000];
int n;

int path_k(int e) {
	int k=0;
	node head;
	head.num = e;
	head.step = 0;
	queue<node> q;
	q.push(head);
	while (!q.empty()) {
		node front=q.front();
		node next;
		int flag = 0;
		for (int i = 0; i < n; i++) {
			if (edge[front.num][i] != 0&&edge[i][front.num]!=0) {
				flag = 1;
				if (!vis[front.num][i]) {
					next.num = i;
					next.step = front.step + 1;
					if (next.step > k) k = next.step;
					q.push(next);
					vis[front.num][i] = true;
					vis[i][front.num] = true;
				}
			}
		}
		if (flag == 0) return -1;
		q.pop();
	}
	return k;
}

int main() {
	while (scanf("%d",&n) && n != 0) {
		map<string, int> peop;
		string s;
		for (int i = 0; i < n; i++) {
			cin >> s;
			//scanf("%s", s.c_str());
			peop[s] += i;
		}
		int m;
		cin >> m;
		for (int i = 0; i < m; i++) {
			string s1, s2;
			cin >> s1 >> s2;
			//scanf("%s %s", s1.c_str(),s2.c_str());
			edge[peop[s1]][peop[s2]] = 1;
			edge[peop[s2]][peop[s1]] = 1;
		}
		int k=0;
		for (int i = 0; i < n; i++) {
			memset(vis, false, sizeof(vis));
			int temp = path_k(i);
			if (temp == -1) {
				k = -1;
				break;
			}
			else if (temp > k) {
				k = temp;
			}
		}
		//cout << k << endl;
		printf("%d\n", k);
	}
	return 0;
}

但是这段代码在oj上会报出TimeLimitedExceed的错误，说明采用的方法有待改进,手写队列并稍作优化后，仍然会有TLE的错误…
大佬救我
代码奉上

#pragma warning(disable:4996)
#include<iostream>
#include<string>
#include<map>
using namespace std;

struct node {
	int num;
	int step;
};
int edge[1000][1000] = {0};//用来记录边的连接情况
bool vis[1000];
int n;

int path_k(int e) {
	node q[1000];
	int k=0;
	node head;
	head.num = e;
	head.step = 0;
	//queue<node> q;
	int top=0, tail=0;
	//q.push(head);
	q[tail++] = head;
	vis[e] = true;
	while (top!=tail) {
		node front=q[top++];
		node next;
		int flag = 0;
		for (int i = 0; i < n; i++) {
				if (edge[front.num][i] != 0 && edge[i][front.num] != 0) {
					flag = 1;
					if (!vis[i]) {
						next.num = i;
						next.step = front.step + 1;
						if(next.step>6) return -1;
						if (next.step > k) k = next.step;
						q[tail++] = next;
						vis[i] = true;
					}
				}
		}
		if (flag == 0) return -1;
	}
	return k;
}

int main() {
	while (scanf("%d",&n) && n) {
		memset(edge, 0, sizeof(edge));
		map<string, int> peop;
		string s;
		for (int i = 0; i < n; i++) {
			cin >> s;
			//scanf("%s", s);
			peop[s] += i;
		}
		int m;
		scanf("%d", &m);
		for (int i = 0; i < m; i++) {
			string s1, s2;
			cin >> s1 >> s2;
			//scanf("%s %s", s1.c_str(),s2.c_str());
			edge[peop[s1]][peop[s2]] = 1;
			edge[peop[s2]][peop[s1]] = 1;
		}
		int k=0;
		for (int i = 0; i < n; i++) {
			memset(vis, false, sizeof(vis));
			int temp = path_k(i);
			if (temp == -1) {
				k = -1;
			}
			else if (temp > k&&k!=-1) {
				k = temp;
			}
		}
		//cout << k << endl;
		printf("%d\n", k);
	}
	return 0;
}