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]);
}
}