51nod1676-无向图同构【乱搞】
2024-10-19 12:39:48
正题
题目连接:http://www.51nod.com/Challenge/Problem.html#problemId=1676
题目大意
给出两张\(n\)个点\(m\)条边的无向图,求这两张图是否同构。
\(1\leq n\leq 200,1\leq m\leq 4000,1\leq T\leq 20\)
解题思路
方法应该有挺多的,反正大概就是要找到这张图的与编号无关的信息。
这里用的是路径数量,对于\(i\in[1,n]\)我们求出每个点出发长度为\(i\)的路径数量,然后排序比较就好了。
应该找不到反例,找个比较奇怪的质数应该就卡不掉了。
时间复杂度\(O(Tnm)\)
code
#include<cstdio>
#include<cstring>
#include<algorithm>
#define ll long long
using namespace std;
const ll N=4100,P=1145141;
ll n,m,T,ans,x[N],y[N],a[N],b[N],X[N],Y[N],f[2][N],g[2][N];
signed main()
{
scanf("%lld",&T);
while(T--){
scanf("%lld%lld",&n,&m);ans=1;
for(ll i=1;i<=m;i++)scanf("%lld%lld",&x[i],&y[i]);
for(ll i=1;i<=m;i++)scanf("%lld%lld",&X[i],&Y[i]);
for(ll i=1;i<=n;i++)f[0][i]=g[0][i]=1;
for(ll i=1;i<=n;i++){
for(ll j=1;j<=n;j++)
f[i&1][j]=f[~i&1][j],g[i&1][j]=g[~i&1][j];
for(ll j=1;j<=m;j++){
(f[i&1][x[j]]+=f[~i&1][y[j]])%=P;
(f[i&1][y[j]]+=f[~i&1][x[j]])%=P;
(g[i&1][X[j]]+=g[~i&1][Y[j]])%=P;
(g[i&1][Y[j]]+=g[~i&1][X[j]])%=P;
}
for(ll j=1;j<=n;j++)
a[j]=f[i&1][j],b[j]=g[i&1][j];
sort(a+1,a+1+n);sort(b+1,b+1+n);
for(ll j=1;j<=n;j++)
if(a[j]!=b[j]){ans=0;break;}
if(!ans)break;
}
if(ans)puts("YES");
else puts("NO");
}
return 0;
}
最新文章
- java基础算法之插入排序
- VS2013如何避开安装时IE10的限制
- [ios]关于用FMDB 操作数据库 删除 tableView 后刷新
- &ldquo;Stamping&rdquo; PDF Files Downloaded from SharePoint 2010
- linux使用dd命令快速生成大文件
- Sencha CMD 4- 安装与首次使用
- C++中cin、cin.get()、cin.getline()、getline()、gets()等函数的用法----细节决定成败 (sort用法)
- Oracle Length 和 Lengthb 函数说明 .(用来判断记录值里是否有中文内容)
- 安装完Kali linux 之后 需要配置的一些 常用软件 记录
- 【HDU4333】Revolving Digits(扩展KMP+KMP)
- SmartQQ二维码登陆接口分析
- 201521123107 《Java程序设计》第1周学习总结
- UVA11039-Building designing
- django模板导入外部js和css等文件
- Vue与Element走过的坑。。。。带上Axios
- 冒泡,选择,插入,快速排序在Java中的实现
- 【BZOJ3832】[POI2014]Rally(拓扑排序,动态规划)
- hdu_1086 You can Solve a Geometry Problem too(计算几何)
- 国行ME860刷MIUI3.9.27
- 大量数据导入导致mysql自动重启