uoj175 【Goodbye Yiwei】新年的网警

胡乱分析

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

}

巴特西

uoj175 【Goodbye Yiwei】新年的网警

最新文章

热门文章