讨论 / 一种解法
Y阿杜 2015-12-23 21:48:14
点我顶贴 收藏 删除
#include <iostream>

using std::cin;

using std::cout;

template<class Type>

class stack

{

private:

Type *data;

int head;

public:

stack(int n) { data = new Type[n]; head = -1; }

~stack() { delete[]data; }

void push(Type d) { data[++head] = d; }

void pop() { head--; }

Type top() { return data[head]; }

bool empty() { return head == -1; }

};

int main()

{

int N, *parent;

int tmp1, tmp2;

cin >> N;

stack<int> path1(N+1), path2(N+1);

parent = new int[N+1];

for (int i = 0; i <= N; ++i)parent[i] = 0;

for (int i = 1; i < N; ++i) {

cin >> tmp1 >> tmp2;

parent[tmp2] = tmp1;

}

int pos1, pos2;

cin >> pos1 >> pos2;

if (pos1 == pos2) {

cout << pos1; return 0;

}

while (pos1 != 0) {

path1.push(pos1);

pos1 = parent[pos1];

}

while (pos2 != 0) {

path2.push(pos2);

pos2 = parent[pos2];

}

int result = path1.top();

while (path1.top() == path2.top()) {

result = path1.top();

path1.pop(); path2.pop();

}

cout << result;

delete[]parent;

return 0;

}

查看更多回复
提交回复