hihoCoder 1507-可疑的记录

hihoCoder 1507-可疑的记录

#1507 : 可疑的记录

时间限制:10000ms
单点时限:1000ms
内存限制:256MB

描述

小Hi有一棵N个节点的树,编号1-N,其中1号节点是整棵树的根。他把这棵树的N-1条边记录成N-1行,每行2个整数a和b,表示a是b的父节点。

喜欢恶作剧的小Ho在小Hi的记录里加了一行两个整数,于是小Hi不得设法找出这行可疑的记录。具体来说,如果去掉某一行之后,余下N-1行按小Hi的规则(a是b的父节点)恰好能构成一棵N个节点的树,并且满足编号恰好是1-N且1号节点是根,那么被去掉的一行就被视为可疑的。

你能帮小Hi找出所有可疑的记录吗?

输入

第一行包含一个整数N,表示树的节点数目。

以下N行每行两个整数a和b,表示a是b的父节点。

对于30%的数据,1 <= N <= 1000

对于100%的数据, 1 <= N <= 100000, 1 <= a, b <= N

输入保证合法。

输出

输出一行包含若干个从小到大的整数,表示可疑的行号。(行号从1开始)

样例输入
3
1 2
1 3
1 3
样例输出
2 3

有一棵编号从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. 最后,正常的树中除了根节点,每个节点有且仅有一个父亲节点,如果添加了一行,且不满足上面两种情况,则肯定会出现某个点的父亲节点有两个!所以我们只需要找出出现两个父亲节点的节点即可,而且这两个父亲都有可疑。

根据上述三条规则,马上写出代码:

#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;
}

本代码提交AC,用时253MS。

Leave a Reply

Your email address will not be published. Required fields are marked *