爱彼迎19年社招java面试题 求DAG图中每个点的祖先个数

缘起

群里一个小妹妹面试爱彼迎的时候被问到的. 题目RT

例如上图, 则H的祖先个数是3个（包括它自己哈），分别是S和A. 而N的祖先个数是4（S/E/A/N）。

分析

此题比较tricky的地方在于N的祖先S和E的祖先可能是同一个（A）但是又不能重复计数. 所以我们需要在每个顶点上维护一个HashSet. 用于记录它的祖先集合, 伊始，集合仅仅有他自己. 然后反向建图. 最后从叶子节点（即伊始出度为0的点）开始dfs. 既然是反向建图，那么求祖先就转变为求孩子的个数了. 则每从一个节点退出dfs搜索之后就可以打印答案了. 假设输入格式如下

1
2
3
4
3
A,S,E,N
S,H,N
E,N

第一行是弧的条数. 后面每一行第一个字符是弧的起点, 后面都是弧的终点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
#include "stdafx.h"
#include <stdio.h>
#include <vector>
#include <set>
using namespace std;

vector<int> g[30]; //g是反向图
vector<int> root;  // root收集了反向图的根节点
set<int> a[30]; // a[i]是顶点i的祖先集合
char s[30];
int indeg[30]; // 用于找出根节点
bool v[30]; // 哪些字母出现过

typedef vector<int>::iterator vit;

void dfs(int cur)
{
	for (vit x = g[cur].begin(); x!=g[cur].end(); x++)
	{
		dfs(*x);
		a[cur].insert(a[*x].begin(), a[*x].end());
	}
}

int main()
{
	freopen("d:\\data.in", "r", stdin);
	int n;
	scanf("%d", &n);
	for (int i = 0;i<30; i++)
	{
		a[i].insert(i);
	} // 伊始集合中只有自己
	while(n--)
	{
		scanf("%s", s);
		int b = s[0]-'A';
		v[b] = true;
		for (int i = 1;s[i]; i++)
		{
			if (s[i]==',')
			{
				continue;
			}
			g[s[i]-'A'].push_back(b);
			v[s[i]-'A'] = true;
			indeg[b]++;
		} // 反向建图
	}
	for (int i = 0;i<30;i++)
	{
		if (!indeg[i]&&v[i])
		{
			root.push_back(i);
		}
	} // 收集根节点
	for (vit x = root.begin(); x!=root.end(); x++)
	{
		dfs(*x);
	}
	for (int i = 0; i<30; i++)
	{
		if (v[i])
		{
			printf("%c的祖先有%d个\n", i+'A', a[i].size());
		}
	}
	return 0;
}

测试数据如下

1
2
3
4
3
A,S,E,N
S,H,N
E,N

运行结果

反正也不能提交, 也不晓得到底对不对，但是思路应该是正确的.

ps: 其实本题是有实际背景的—— 大家知道，maven项目管理的时候, 一个项目的字节码异动可能会导致多个项目重新要打包. 现在公司有若干项目，互相依赖（当然，不会有环形依赖），要你计算每个项目（记做P）的字节码修改会导致重新打包的项目的数量（包括P自己）

并不是爱彼迎变着法考算法，而是算法本身就来源于生活，抽象于生活。所以算法的力量是很大的