网站建设移动网络,seo方案,嘉峪关建设厅官方网站,西部数码做跳转网站正题
题目连接:http://www.51nod.com/Challenge/Problem.html#problemId1676 题目大意
给出两张nnn个点mmm条边的无向图#xff0c;求这两张图是否同构。 1≤n≤200,1≤m≤4000,1≤T≤201\leq n\leq 200,1\leq m\leq 4000,1\leq T\leq 201≤n≤200,1≤m≤4000,1≤T≤20 解题…正题
题目连接:http://www.51nod.com/Challenge/Problem.html#problemId1676 题目大意
给出两张nnn个点mmm条边的无向图求这两张图是否同构。
1≤n≤200,1≤m≤4000,1≤T≤201\leq n\leq 200,1\leq m\leq 4000,1\leq T\leq 201≤n≤200,1≤m≤4000,1≤T≤20 解题思路
方法应该有挺多的反正大概就是要找到这张图的与编号无关的信息。
这里用的是路径数量对于i∈[1,n]i\in[1,n]i∈[1,n]我们求出每个点出发长度为iii的路径数量然后排序比较就好了。
应该找不到反例找个比较奇怪的质数应该就卡不掉了。
时间复杂度O(Tnm)O(Tnm)O(Tnm) code
#includecstdio
#includecstring
#includealgorithm
#define ll long long
using namespace std;
const ll N4100,P1145141;
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);ans1;for(ll i1;im;i)scanf(%lld%lld,x[i],y[i]);for(ll i1;im;i)scanf(%lld%lld,X[i],Y[i]);for(ll i1;in;i)f[0][i]g[0][i]1;for(ll i1;in;i){for(ll j1;jn;j)f[i1][j]f[~i1][j],g[i1][j]g[~i1][j];for(ll j1;jm;j){(f[i1][x[j]]f[~i1][y[j]])%P;(f[i1][y[j]]f[~i1][x[j]])%P;(g[i1][X[j]]g[~i1][Y[j]])%P;(g[i1][Y[j]]g[~i1][X[j]])%P;}for(ll j1;jn;j)a[j]f[i1][j],b[j]g[i1][j];sort(a1,a1n);sort(b1,b1n);for(ll j1;jn;j)if(a[j]!b[j]){ans0;break;}if(!ans)break;}if(ans)puts(YES);else puts(NO);}return 0;
}
