在大学做网站赚钱吗,建设网站协议合同范本,龙岗做网站多少钱,手机必备app排行榜#x1f468;#x1f3eb; 5133. 奶牛排队
题目描述
约翰的农场有 n n n 头奶牛#xff0c;每一头奶牛都有一个正整数编号。
不同奶牛的编号不同。
现在#xff0c;这 n n n 头牛按某种顺序排成一队#xff0c;每头牛都拿出一张纸条写下了其前方相邻牛的编号以及其… 5133. 奶牛排队
题目描述
约翰的农场有 n n n 头奶牛每一头奶牛都有一个正整数编号。
不同奶牛的编号不同。
现在这 n n n 头牛按某种顺序排成一队每头牛都拿出一张纸条写下了其前方相邻牛的编号以及其后方相邻牛的编号。
注意
这些奶牛并没有记下自己的编号。位于队首的奶牛前方没有牛所以它在前方相邻牛处写下的是数字 0 0 0。位于队尾的奶牛后方没有牛所有它在后方相邻牛处写下的是数字 0 0 0。
将所有奶牛写下的纸条收集起来并打乱顺序后交给你。
你的任务是根据这些纸条信息推导出完整的奶牛队列。
输入格式
第一行包含整数 n n n表示奶牛数量。
接下来 n n n 行每行包含两个整数 a _ i , b _ i a\_i,b\_i a_i,b_i表示其中一头奶牛写下的其前方相邻牛的编号以及其后方相邻牛的编号。
注意 a _ i a\_i a_i 或 b _ i b\_i b_i 可能为 0 0 0这表示该奶牛没有前方相邻牛或后方相邻牛。
输出格式
输出共一行 n n n 个整数按照从前到后的顺序输出队列中每头奶牛的编号。
数据范围
前 5 5 5 个测试点满足 2 ≤ n ≤ 5 2 \le n \le 5 2≤n≤5。 所有测试点满足 2 l e n ≤ 2 × 1 0 5 2 \\le n \le 2 \times 10^5 2len≤2×105 0 ≤ a _ i , b _ i ≤ 1 0 6 0 \le a\_i,b\_i \le 10^6 0≤a_i,b_i≤106。
输入样例
4
92 31
0 7
31 0
7 141输出样例
92 7 31 141时间复杂度
O(n) AC code
import java.util.Scanner;public class Main
{static int N 1000010;static int[] a new int[N];static int[] b new int[N];static int[] mp new int[N];static int[] cnt new int[N];// 记录每个数出现的次数出现在前面 1出现在后面 -1public static void main(String[] args){Scanner sc new Scanner(System.in);int n sc.nextInt();int idx 0;// idx 记录当前牛在 a[i] 时 的下标 ifor (int i 0; i n; i){a[i] sc.nextInt();b[i] sc.nextInt();cnt[a[i]];cnt[b[i]]--;mp[a[i]] i;if (a[i] 0)// 说明是第一头牛idx i;}int val 0;// val记录当前的值for (int i 0; i N; i)if (cnt[i] 1)val i;//for (int i 0; i n; i){System.out.print(val );int nextVal b[idx];// 当前牛的下标 idx 的 b后一位int nextIdx mp[val];// 找到 下一头牛的编号 a[i] 的 下标 ival nextVal;idx nextIdx;}}
}
