hihoCoder 1507-可疑的记录

---

有一棵编号从1~N的树，其中根节点为1。这棵树的n-1条边用n-1行x y表示，其中x是y的父亲节点。现在小Ho在其中增加了一行，导致不满足上述性质，要求找出增加的那行。 这一题我用了BFS，DFS等乱七八糟的方法，最终WA。。。看过大神的代码之后，其实这题根本不需要用这些高深的策略，因为只添加了一行，所以用一些简单的规则即可找出。

1. 首先，如果这一行x,y中y如果出现1，则这一行肯定是有问题的，因为1是根节点，不可能在右边。
2. 其次，如果出现x==y，也有问题，因为树没有自回路。
3. 最后，正常的树中除了根节点，每个节点有且仅有一个父亲节点，如果添加了一行，且不满足上面两种情况，则肯定会出现某个点的父亲节点有两个！所以我们只需要找出出现两个父亲节点的节点即可，而且这两个父亲都有可疑。

根据上述三条规则，马上写出代码： [cpp] #include<iostream> #include<cstdlib> #include<algorithm> #include<vector> #include<queue> #include<string> #include<unordered_map> #include<unordered_set> using namespace std; int n, x, y; int main() { //freopen("input.txt", "r", stdin); scanf("%d", &n); vector<int> xarry(n + 1, 0), yarry(n + 1, 0); for (int i = 0; i < n; ++i) { scanf("%d %d", &xarry[i], &yarry[i]); } vector<vector<int>> parent(n + 1, vector<int>()); for (int i = 0; i < n; ++i) { if (yarry[i] == 1) { // 根节点不可能在右边 printf("%d\n", i + 1); break; } if (xarry[i] == yarry[i]) { // 没有自回路 printf("%d\n", i + 1); break; } parent[yarry[i]].push_back(i + 1); } for (int i = 1; i <= n; ++i) { if (parent[i].size() > 1) { printf("%d %d ", parent[i][0], parent[i][1]); break; // 因为只添加了一行，所以只可能有一个节点有两个父亲 } } return 0; } [/cpp] 本代码提交AC，用时253MS。]]>