uoj175 【Goodbye Yiwei】新年的网警

时间:2023-01-15 21:04:44

题目

胡乱分析

不妨定谣言的源头得到谣言的时刻为\(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;
}