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

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