PAT 1110

#include<cstdio> #include<iostream> #include<string> #include<vector> #include<algorithm> #include<string> #include<queue> using namespace std; const int maxn = 1000; struct Node { int lchild, rchild; }node[maxn]; bool table[maxn] = {false}; int test[maxn]; int k = 0; void bfs(int root) { queue<int> q; q.push(root); while (!q.empty()) { int top = q.front(); q.pop(); test[k++] = top; if (k > 100) return; if (top != -1) { q.push(node[top].lchild); q.push(node[top].rchild); } } } int main() { int n; cin >> n; fill(test,test+maxn,-1); string a, b; for (int i = 0;i < n;i++) { cin >> a >> b; if (a.size()==1&&a[0] != '-') { node[i].lchild = a[0] - '0'; table[a[0] - '0'] = true; } else if (a.size() == 1 && a[0] == '-') node[i].lchild = -1; else if (a.size() == 2) { node[i].lchild = (a[0] - '0') * 10 + a[1] - '0'; table[node[i].lchild] = true; } if (b.size()==1&&b[0] != '-') { node[i].rchild = b[0] - '0'; table[b[0] - '0'] = true; } else if(b.size()==1&&b[0]=='-') node[i].rchild = -1; else if (b.size()==2) { node[i].rchild = (b[0] - '0') * 10 + b[1] - '0'; table[node[i].rchild] = true; } } int root; for (int i=0;i<n;i++) { if (table[i] == false) { root = i; break; } } bfs(root); for (int i=0;i<n;i++) { if (test[i] == -1) { cout << "NO "<<root; system("pause"); return 0; } } cout << "YES " << test[n - 1]; system("pause"); return 0; }