比赛 |
20110923 |
评测结果 |
MMMMMMMMMM |
题目名称 |
拜访奶牛 |
最终得分 |
0 |
用户昵称 |
magic |
运行时间 |
0.000 s |
代码语言 |
C++ |
内存使用 |
0.00 MiB |
提交时间 |
2011-09-23 20:50:24 |
显示代码纯文本
#include<iostream>
#include<cstdio>
using namespace std;
struct Node
{
int son[1000];
int p;
};
Node node[50005];
int num[50005];
int nod[50005];
bool flag[50005];
int a,b,n,ans=0;
void qsort(int a[],int l,int r);
void qsort(int a[],int l,int r)
{
int i,j,x,y;
i=l;j=r;x=a[(l+r)/2];
while (i<=j)
{
while (a[i]<x) i++;
while (a[j]>x) j--;
if (i<=j)
{
y=a[i];a[i]=a[j];a[j]=y;
y=nod[i];nod[i]=nod[j];nod[j]=y;
i++;j--;
}
}
if (l<j) qsort(a,l,j);
if (i<r) qsort(a,i,r);
}
int main()
{
freopen("vacation.in","r",stdin);
freopen("vacation.out","w",stdout);
scanf("%d",&n);
for (int i=1;i<=n;i++)
{
nod[i]=i;
}
for (int i=1;i<=n-1;i++)
{
scanf("%d%d",&a,&b);
num[a]++;
num[b]++;
node[a].p++;
node[b].p++;
node[a].son[node[a].p]=b;
node[b].son[node[b].p]=a;
}
qsort(num,1,n);
for (int i=1;i<=n;i++)
{
if (!flag[i])
{
ans++;
for (int j=1;j<=node[i].p;j++)
{
flag[node[i].son[j]]=1;
}
}
}
/*for (int i=1;i<=n;i++)
{
printf("%d ",num[i]);
}
for (int i=1;i<=n;i++)
{
printf("%d ",nod[i]);
}*/
printf("%d",ans);
return 0;
}