胡乱分析
不妨定谣言的源头得到谣言的时刻为\(1\)，那么其他人听到谣言的时间就是源头到这个点的最短路
假设\(i\)是谣言的源头，那么如果存在一个点\(j\)满足\(\forall k\in[1,n],k\neq i,k\neq j,dis_{i,k}=dis_{j,k}\)；那么\(i\)只需要说他听到谣言的时间为\(dis_{i,j}\)，就无法判断\(i,j\)哪一个是谣言的源头了
这个\(\forall k\in[1,n],k\neq i,k\neq j,dis_{i,k}=dis_{j,k}\)条件看起来不是很好做，但是由于这张图的边权都是\(1\)，只需要\(i\)和\(j\)第一遍松弛的点相同，即和\(i,j\)直接相连的点相同，跑出来的最短路就一定相同
于是我们只需要对每个点维护一下与其直接相连的点集，判断两个点集是否相等自然可以直接hash一波
之后收获了大零蛋的好成绩
进一步胡乱分析发现，如果一个点的度数为\(1\)或者与度数为\(1\)的点相连，那么这个点也无法被确定为嫌疑人。
当度数为\(1\)的点的人为源头时，他只需要说他收到谣言的时间为\(3\)，就无法确定这个点和与他相连的点哪一个是真正的源头；反之同理。
代码
#include<bits/stdc++.h>
#include<tr1/unordered_map>
#define re register
#define uint unsigned long long
using namespace std::tr1;
inline int read() {
char c=getchar();int x=0;while(c<'0'||c>'9') c=getchar();
while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+c-48,c=getchar();return x;
}
const int maxn=1e5+5;
uint base=200019;
unordered_map<uint,int> ma[2];
std::vector<int> v[maxn],d[maxn];
uint ha[2][maxn];int n,m,vis[maxn],dg[maxn];
inline void add(int x,int y) {
v[x].push_back(y),v[y].push_back(x);
d[x].push_back(y),d[y].push_back(x);
dg[x]++,dg[y]++;
}
int main() {
int T=read();
while(T--) {
for(re int i=1;i<=n;i++) v[i].clear(),d[i].clear(),ha[0][i]=ha[1][i]=0,dg[i]=0;
n=read(),m=read(); ma[0].clear(),ma[1].clear();
for(re int x,y,i=1;i<=m;i++)
x=read(),y=read(),add(x,y);
for(re int i=1;i<=n;i++) {
d[i].push_back(i);
std::sort(v[i].begin(),v[i].end());
std::sort(d[i].begin(),d[i].end());
for(re int j=0;j<v[i].size();++j)
ha[0][i]=ha[0][i]*base+v[i][j];
ma[0][ha[0][i]]++;
for(re int j=0;j<d[i].size();++j)
ha[1][i]=ha[1][i]*base+d[i][j];
ma[1][ha[1][i]]++;
}
int ans=0;
for(re int i=1;i<=n;i++) if(dg[i]==1||ma[0][ha[0][i]]>1||ma[1][ha[1][i]]>1) vis[i]=T+1,++ans;
for(re int i=1;i<=n;i++)
if(vis[i]!=T+1) {
for(re int j=0;j<v[i].size();j++)
if(dg[v[i][j]]==1) {vis[i]=T+1;++ans;break;}
}
printf("%d\n",ans);
for(re int i=1;i<=n;i++) if(vis[i]==T+1) printf("%d ",i);puts("");
}
return 0;
}