北邮OJ-92. 统计节点个数-13计院上机B

本文主要是介绍北邮OJ-92. 统计节点个数-13计院上机B，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

最终算法：
使用树模型，建立完整的包含父节点与子节点的树结构，这是为了后面在遍历比较与父与子的时候能够找到父找到子。然后关于degree的计算，
在输入父子关系的时候可以直接把父与子的degree分别+1（因为求的是总度，可以看成无向图的顶点的度来处理）。
错误建模：
1.使用了并查集模型：错误在于只能记录父节点而不能记录子节点
2.使用了图模型：错误在于把树转化为图之后，要把简单的父子关系转化为每个顶点的边集，很是麻烦，模型本身就不对

题目描述
给出一棵有向树，一共有N(1

#include <iostream>
#include <cstdio>
#include <vector>
#define MAXSIZE 1010
#define data father
using namespace std;
typedef struct Node{int data;vector<int> sonList;bool turnOn;Node(){//initiate automatically except data initNode();}void initNode(){turnOn=false;sonList.clear();}
}*Tree;
Node treeList[MAXSIZE];
int cursor;
int degree[MAXSIZE];int createNode(int data){//return the index of new node if (cursor+1==MAXSIZE)return -1;//failedint nowP=cursor;cursor++;
//  treeList[nowP].initNode();treeList[nowP].turnOn=true;treeList[nowP].data=data;return nowP;
}
int createNode(int data,int index){//return the index of new node 
//  treeList[nowP].initNode();treeList[index].turnOn=true;treeList[index].data=data;return index;
}
void freeNode(int index){treeList[index].initNode();
}
void freeTree(int index){//postOrderif (index!=-1){//traverseNode &nowN=treeList[index];for (int i=0;i<nowN.sonList.size();i++){freeTree(nowN.sonList[i]);}//visitfreeNode(index);}
}
int main(){int t,n;int x,y;int count;scanf("%d",&t);while (t--){//initiatefor (int i=0;i<MAXSIZE;i++){treeList[i].initNode();}cursor=0;for (int i=0;i<n;i++){degree[i]=0;}count=0;//inputscanf("%d",&n);for (int i=0;i<n-1;i++){scanf("%d%d",&x,&y);//Í³¼Æ½ÚµãÊý degree[x]++;degree[y]++;if (treeList[x].turnOn!=true){//Èô´Ë¸¸½ÚµãÉÐÎ´½¨Á¢ createNode(-1,x);//Ôò´´½¨ }treeList[x].sonList.push_back(y);if (treeList[y].turnOn!=true){//Èô´Ë½ÚµãÉÐÎ´´´½¨ createNode(x,y);//Ôò´´½¨ }           }//searchfor (int i=0;i<n;i++){//±éÀúËùÓÐ½áµã£¬ÅÐ¶ÏÆäÊÇ·ñÊÇp½áµã Node &nowNode=treeList[i];bool isP=true;if (degree[i]<degree[nowNode.data])isP=false;else{for (int j=0;j<nowNode.sonList.size();j++){if (degree[i]<degree[nowNode.sonList[j]]){isP=false;break;}}}if (isP==true)count++;}//outputprintf("%d\n",count);}return true;
}