首页 > 代码库 > hihocoder [Offer收割]编程练习赛14 可疑的记录

hihocoder [Offer收割]编程练习赛14 可疑的记录

题目3 : 可疑的记录

时间限制: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开始)

样例输入
31 21 31 3
样例输出
2 3
EmacsNormalVim
//要么一个点有两个father,要么根有father,暴力验证一下这几条可能的边就出来了#include<cstdio>#include<vector>using namespace std;const int N=1e5+5;int n,a[N],b[N];vector<int>fa[N];int main(){    scanf("%d",&n);    for(int i=1;i<=n;i++) scanf("%d%d",a+i,b+i);    for(int i=1;i<=n;i++){        if(a[i]==b[i]){printf("%d\n",i);return 0;}        if(1==b[i]){printf("%d\n",i);return 0;}        fa[b[i]].push_back(i);    }    for(int i=1;i<=n;i++) if(fa[i].size()>1){        printf("%d %d\n",fa[i][0],fa[i][1]);        return 0;    }    return 0;}

 

 

 

 

hihocoder [Offer收割]编程练习赛14 可疑的记录