小米2013年招聘笔试算法题--朋友圈

int32位 posted @ Oct 28, 2013 04:55:50 PM in algorithm , 3565 阅读
转载请注明:http://krystism.is-programmer.com/若有错误,请多多指正,谢谢!

题目描述:假如已知有n个人和m对好友关系(存于数字r)。如果两个人是直接或间接的好友(好友的好友的好友...),则认为他们属于同一个朋友圈,请写程序求出这n个人里一共有多少个朋友圈。

假如:n = 5 , m = 3 , r = {{1 , 2} , {2 , 3} , {4 , 5}},表示有5个人,1和2是好友,2和3是好友,4和5是好友,则1、2、3属于一个朋友圈,4、5属于另一个朋友圈,结果为2个朋友圈。 最后请分析所写代码的时间、空间复杂度。评分会参考代码的正确性和效率。

显然本质就是求无向图的连通分量个数。而要求连通分量数,就是遍历图的过程。遍历完所有节点,需要调用遍历几次就是连通分量个数。比如题目中使用DFS,从节点1出发,可以遍历节点2,3,而要遍历完所有节点还需从节点4出发,再遍历一次,共遍历两次,因此连通分量数为2。实现代码如下:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define N 10000
char map[N][N];
char used[N];
void dfs(int i, int n)
{
	int j;
	used[i] = 1;
	for(j = 1; j <= n; j++) {
		if (map[i][j] && !used[j])
			dfs(j, n);
	}
}
/* 判断是否存在未访问节点
 * 若存在,则返回第一个未访问节点编号
 * 若不存在,则返回-1
 */
int isVisitedAll(int n)
{
	int i;
	for (i = 1; i <= n; i++)
		if (used[i] == 0)
			return i;
	return -1;
}
int main(int argc, char **argv)
{
	int n, m;
	int a, b, i, sum, cur;
	while (scanf("%d%d", &n, &m) != EOF) {
		if (n == 0)
			break;
		memset(map, 0, sizeof(map));
		memset(used, 0, sizeof(used));
		sum = 0;
		for (i = 0; i < m; i++) {
			scanf("%d%d", &a, &b);
			map[a][b] = map[b][a] = 1;
		}
		while((cur = isVisitedAll(n)) != -1) {
			sum++;
			dfs(cur, n);
		}
		printf("%d\n", sum);
	}
	return 0;
}

暂且不说时间复杂度吧,空间复杂度就足够吓人了。首先需要一个表示图的01矩阵,大小为O(n  * n), 还需要记录是否节点是否已经被访问,需要大小为O(n)的空间。

换一种思路,其实根据题目朋友圈,我们就应该想到每一个圈其实就是一个集合,存在关系的,归为一个集合中,最后即需要求有多少个不相交的集合即有多少个圈子。由此不难想出,这其实就是并查集。不了解并查集可以查看维基百科并查集

想到了并查集,不难写出代码:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define N 100000
int father[N];
void init(int n)
{
	int i;
	for (i = 1; i <= n; i++)
		father[i] = i;
}
int getFather(int v)
{
	if (father[v] == v)
		return v;
	else {

		father[v] = getFather(father[v]);
		return father[v];
	}
}
void merge(int x, int y)
{
	int fx = getFather(x);
	int fy = getFather(y);
	if (fx < fy)
		father[fx] = fy;
	else
		father[fy] = fx;
}
int same(int x, int y)
{
	return getFather(x) == getFather(y);
}
int main(int argc, char **argv)
{
	int n, m;
	int a, b;
	int i;
	int sum;
	while (scanf("%d%d", &n, &m) != EOF) {

		if (n == 0)
			break;
		init(n);
		sum = 0;
		for (i = 1; i <= m; i++) {
			scanf("%d%d", &a, &b);
			merge(a, b);
		}
		for (i = 1; i <= n; i++) {
			if (getFather(i) == i)
				sum++;
		}
		printf("%d\n", sum);
	}
	return 0;
}

显然空间大大减少了,只需要O(n)的空间。

转载请注明:http://krystism.is-programmer.com/若有错误,请多多指正,谢谢!
  • 无匹配
  • 无匹配

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter