zstu 3999

自己学校OJ上的一道水题，但我却WA、TLE了好多次。查来查去，问来问去，才发现了没有初始化重置数据。。。

收获：问了杰神之后，开始学会用数组或者容器vector来表示邻接表（之前我居然用list的。。。）

由于一开始不知道哪个点才是起点，因此要建立双向边！

数组：

head[N]//初始化为-1；

}edge[N<<1];

void init() {    memset(head, -1, sizeof(head));    E = 0;//E是与head相邻点的个数

}void newedge(int u, int v) {    edge[E].v = v;edge[E].next = head[u];    head[u] = E++;}

vector：

vector a[SIZE];

vector :: iterator endd = a[root].end();//迭代器    for(vector:: iterator i = a[root].begin(); i !=endd; i++)    {        cot[root] += dfs(*i);    }

常用方法：

vector.push_back(i);

vector.size();

vector.empty();

vector.clear();

vector.end();

vector.begin();

本题AC代码：

#include 
#include 
#include 
#include 
using namespace std;
const int SIZE = 10005;
int mark[SIZE],cot[SIZE];
vector  a[SIZE];
int dfs(int root)
{mark[root] = 1;if(a[root].size() == 0){cot[root] = 1;return 1;}vector :: iterator endd = a[root].end();for(vector:: iterator i = a[root].begin(); i !=endd; i++){if(mark[*i])continue;cot[root] += dfs(*i);}cot[root]++;return cot[root];
}
int main()
{int n,m;while(scanf("%d%d",&n,&m)!=EOF){memset(mark,0,sizeof(mark));memset(cot,0,sizeof(cot));int t1,t2;for(int i = 0;i < n-1;i++){scanf("%d%d",&t1,&t2);a[t1].push_back(t2);a[t2].push_back(t1);}mark[m] = 1;dfs(m);int times,xb;scanf("%d",×);for(int i = 0;i < times;i++){scanf("%d",&xb);printf("%d\n",cot[xb]);}for(int i = 0;i <= n;i++){a[i].clear();}}return 0;
}
/*
5 1
4 5
3 2
2 1
1 4
5
1 2 3 4 5
*/

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！