给出一张 $n$ 个点 $m$ 条边的无向连通图，每条边的边权为1。对于每个点 $i$ ，问是否存在另一个点 $j$ ，使得对于任意一个不为 $i$ 或 $j$ 的点 $k$ ，$i$ 到 $k$ 的最短路与 $j$ 到 $k$ 的最短路之差为定值。求所有满足条件的点 $i$ 。
$n\le 100000,m\le 200000$
题解
结论题+Hash
结论：$i$ 满足条件，当且仅当满足三个条件之一：
1. 点 $i$ 的度数为1；
2. 点 $i$ 与一个度数为1的点相连；
3. 存在某个点 $j$ ，使得 $i$ 与 $j$ 和所有除 $i,j$ 以外的点是否有边 相同。
证明参考 这里 。
对于条件1、2很容易判断。
对于3条件我们可以将所有与 $i$ 点相连的点Hash一下即可判断出 $i$ 与 $j$ 没有边的 $j$ 。
再把 $i$ 自己加进去Hash一下即可判断书 $i$ 与 $j$ 有边的 $j$ 。
其中Hash的模数要设成 $10^{18}$ 级别。
时间复杂度为使用map判断的 $O(m+n\log n)$
#include <map>
#include <cstdio>
#include <cstdlib>
#define N 100010
using namespace std;
typedef long long ll;
map<ll , int> mp1 , mp2;
int px[N << 1] , py[N << 1] , c[N] , flag[N] , ans[N];
ll v[N] , a[N] , b[N];
int main()
{
srand(20011011);
int T;
scanf("%d" , &T);
while(T -- )
{
mp1.clear() , mp2.clear();
int n , m , i , tot = 0;
scanf("%d%d" , &n , &m);
for(i = 1 ; i <= n ; i ++ ) v[i] = a[i] = ((ll)rand() << 45) + ((ll)rand() << 30) + (rand() << 15) + rand() , flag[i] = c[i] = b[i] = 0;
for(i = 1 ; i <= m ; i ++ ) scanf("%d%d" , &px[i] , &py[i]) , c[px[i]] ++ , c[py[i]] ++ ;
for(i = 1 ; i <= m ; i ++ )
{
if(c[px[i]] == 1) flag[py[i]] = 1;
if(c[py[i]] == 1) flag[px[i]] = 1;
a[px[i]] ^= v[py[i]] , b[px[i]] ^= v[py[i]];
a[py[i]] ^= v[px[i]] , b[py[i]] ^= v[px[i]];
}
for(i = 1 ; i <= n ; i ++ ) mp1[a[i]] ++ , mp2[b[i]] ++ ;
for(i = 1 ; i <= n ; i ++ )
if(c[i] == 1 || flag[i] || mp1[a[i]] > 1 || mp2[b[i]] > 1)
ans[++tot] = i;
printf("%d\n" , tot);
for(i = 1 ; i <= tot ; i ++ ) printf("%d " , ans[i]);
puts("");
}
return 0;
}