PAT甲級1004 Counting Leaves(30点)

8574 ワード

この木の形の関係の問題は、祖先の関係、師弟の関係のように、最初に考えたのはdfsかそして調査集で、この問題は私が使っているdfsで、コードはとても短くて、セットして、少し修正して基本的にokになりました!
#include
using namespace std;
int child[105]={0};
vector<int> nodes[105];
int maxlevel = 0;
void dfs(int node,int level)
{
	if(nodes[node].size() ==0)
	{child[level] +=1;
	if(level>maxlevel)
	maxlevel = level;
	}
	else
	{
		for(int i=0;i<nodes[node].size();i++)
		dfs(nodes[node][i],level+1);
	
}}
main()
{
	int n,m;
	scanf("%d %d",&n,&m);
	for(int i=0;i<m;i++)
	{
		int id;
		scanf("%d",&id);
		int k;
		scanf("%d",&k);
		for(int j=0;j<k;j++)
		{
			int a;
			scanf("%d",&a);
			nodes[id].push_back(a);
		}
	}
	dfs(1,0);
	for(int i=0;i<=maxlevel;i++)
	{
		if(i==0)
		printf("%d",child[i]);
		else
		printf(" %d",child[i]);
	}
 }