讨论/题目交流/一道笔试碰到过两次的关于图的问题,毫无头绪,求大佬指点/
一道笔试碰到过两次的关于图的问题,毫无头绪,求大佬指点

图的存在性
给定过一个1到N的排列P1​-Pn​,请判断是否存在一个由N个点,N-1条边组成的无向连通图,满足对于任意两个整数i和j(i不等于j),若第i个点和第j个点之间有边相连,则第Pi个点和第Pj​个点之间同样有边相连。

输入:
第一行输入一个整数T表示T组数据,
每组数据格式为:
第一行包括一个整数N,
第二行包含N个整数P1​到PN​

输出:
每组输出一行,如果存在满足条件的图则输出Yes,否则输出No

样例输入:

2
4
4 3 2 1
3
3 1 2

样例输出:

Yes
No

测试数组长度最多高达10^5,所以暴力生成或者检验都不太可能(复杂度np hard)

展开讨论
fengyue723发起于 2019-09-24
最近编辑于 2019-09-26
共 1 个讨论

我倒是有一个想法,但不知道是否正确。
统计P1​-Pn中数字换位形成的环,记录每个环中的点的个数,如果存在单点环或双点环,则存在的这样的图,否则不存在。
比如:
4 3 2 1存在1-4和2-3两个环,都是双点环。
3 1 2存在1-2-3一个环,是三点环。