专栏首页ACM算法日常爱彼迎19年社招java面试题 求DAG图中每个点的祖先个数

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

缘起

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

DAG

例如上图, 则H的祖先个数是3个(包括它自己哈),分别是和. 而N的祖先个数是4()。

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

3
A,S,E,N
S,H,N
E,N

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

#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;
}

测试数据如下

3
A,S,E,N
S,H,N
E,N

运行结果

image

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

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

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

本文分享自微信公众号 - ACM算法日常(acm-clan),作者:影法師の物語

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2019-10-13

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 牛客小白月赛11D(分治、RMQ)

    定义一个玄学节点叫做 R,每次操作读入 val ,执行 Insert(R,val)。

    ACM算法日常
  • 对比 Dijkstra Bellman—Ford Spfa 最短路之间区别

    本质上Dijkstra是一种贪心,满足局部最优,每次找的是离起点最近的(保证了这个点的距离就是最短路),如果有负边权,当前找到的就不一定是最近的了。

    ACM算法日常
  • leetcode题解 | 78. 子集

    这个题目很容易想到使用DFS的方式来解决,因为组合的题容易产生转移方程,这样也是没有什么问题的。

    ACM算法日常
  • 转 算法。

    魂祭心
  • loj#6073. 「2017 山东一轮集训 Day5」距离(费用流)

    我们可以把图行列拆开,同时对于行/列拆成很多个联通块,然后考虑每个点所在的行联通块/列联通块的贡献。

    attack
  • 13:大整数的因子

    13:大整数的因子 查看 提交 统计 提问 总时间限制: 1000ms 内存限制: 65536kB描述 已知正整数k满足2<=k<=9,现给出长度最大为30位...

    attack
  • Java常用排序算法/程序员必须掌握的8大排序算法

    1)插入排序(直接插入排序、希尔排序) 2)交换排序(冒泡排序、快速排序) 3)选择排序(直接选择排序、堆排序) 4)归并排序 5)分配排序(基数排序)

    哲洛不闹
  • NYOJ 139 我排第几个(康拓展开+康拓展开逆运算)

           康拓展开的裸题,对于康拓展开的定义是求当前的排列位于全排列中的第几个,比如132就是123的全排列的第二个,对于康拓展开的求法就是ans = ai...

    Ch_Zaqdt
  • 【HDU 5855】Less Time, More profit(网络流、最小割、最大权闭合子图)

    Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Othe...

    饶文津
  • 算法原理系列:木桶排序

    版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.n...

    用户1147447

扫码关注云+社区

领取腾讯云代金券