#46319: C++ 解法
//Doubly linked list
#include <iostream>
#include <vector>
using namespace std;
struct Node
{
int id;
int Height = 0;
Node* PparentNode = nullptr;
vector<Node*> PchildNode;
};
typedef long long ULONG64;
class TreeAnalyes
{
private:
int id, num, _data, status = 0, TargetValue, countDepth;
ULONG64 SumDepth = 0;
vector<vector<int>> DataArray;
vector<Node*> ChainArray;
vector<Node*> LeastestNode;
Node* TempNode;
public:
TreeAnalyes();
~TreeAnalyes();
void getData();
void appendChild();
void getLeastest();
void getDepth();
void print();
};
int main()
{
char *p = new char[sizeof(TreeAnalyes)];
TreeAnalyes* Tree = new (p) TreeAnalyes;
Tree->getData();
Tree->appendChild();
Tree->getLeastest();
Tree->getDepth();
Tree->print();
Tree->~TreeAnalyes();
delete[] p;
return 0;
}
TreeAnalyes::TreeAnalyes()
{
cin >> id;
DataArray.resize(id);
ChainArray.resize(id);
}
TreeAnalyes::~TreeAnalyes(){
for(int i = 0; i < id; i++){
delete ChainArray[i];
}
DataArray.clear();
vector<vector<int>>().swap(DataArray);
vector<Node*>().swap(ChainArray);
vector<Node*>().swap(LeastestNode);
}
void TreeAnalyes::getData()
{
for (int i = 0; i < id; i++)
{
cin >> num;
if (num == 0)
{
DataArray[i] = {};
continue;
}
for (int j = 0; j < num; j++)
{
cin >> _data;
DataArray[i].push_back(_data);
}
}
}
void TreeAnalyes::appendChild()
{
for (int i = 0; i < id; i++)
{
ChainArray[i] = new Node;
ChainArray[i]->id = i + 1;
}
for (int i = 0; i < id; i++)
{
for (int j = 0; j < DataArray[i].size(); j++)
{
ChainArray[i]->PchildNode.push_back(ChainArray[DataArray[i][j] - 1]);
ChainArray[i]->PchildNode[j]->PparentNode = ChainArray[i];
}
}
}
void TreeAnalyes::getLeastest()
{
for (int i = 0; i < id; i++)
{
if (ChainArray[i]->PparentNode == nullptr)
{
TargetValue = i + 1;
}
if (ChainArray[i]->PchildNode.empty())
{
LeastestNode.push_back(ChainArray[i]);
}
}
}
void TreeAnalyes::getDepth()
{
Node* TempNode;
for (int i = 0; i < LeastestNode.size(); i++)
{
countDepth = 1;
TempNode = LeastestNode[i];
while (TempNode->PparentNode)
{
if (TempNode->Height + 1 > TempNode->PparentNode->Height)
{
TempNode->PparentNode->Height = countDepth;
}
TempNode = TempNode->PparentNode;
countDepth++;
}
}
for (int i = 0; i < id; i++)
{
SumDepth += ChainArray[i]->Height;
}
}
void TreeAnalyes::print()
{
cout << TargetValue << endl
<< SumDepth;
}