https://acm.ecnu.edu.cn/contest/173/problem/C/

联通块染色,若i,j满足题目中的条件,那么他们在每幅图中的染色情况相同,即hash值相同

使用unsigned long long hash 自动对2^64取模;

#include<bits/stdc++.h>
using namespace std;
const int mod=1e9+7;
const int M=1e5+5;
vector<int>e[11][M];
unsigned long long c[11][M],hashh,ans[M];
int vis[M],col;
map<unsigned long long ,int>sign;
void dfs(int deep,int now){
if(vis[now])
return ;
vis[now]=1;
c[deep][now]=col;
for(int i=0;i<e[deep][now].size();i++){
dfs(deep,e[deep][now][i]);
}
}
int main(){
int n,m;
scanf("%d%d",&n,&m);
for(int i=0;i<m;i++){
int k;
scanf("%d",&k);
for(int j=0;j<k;j++){
int x,y;
scanf("%d%d",&x,&y);
e[i][x].push_back(y);
e[i][y].push_back(x);
}
col=0;
memset(vis,0,sizeof(vis));
for(int p=1;p<=n;p++){
if(vis[p])
continue;
col++;
dfs(i,p);
}
}
for(int i=1;i<=n;i++){
hashh=0;
for(int j=0;j<m;j++)
hashh=hashh*mod+c[j][i];
sign[hashh]++;
ans[i]=hashh;
}
for(int i=1;i<=n;i++)
cout<<sign[ans[i]]<<endl;
return 0;
}

  

最新文章

  1. Activity的释放
  2. PostgreSQL Apt Repository
  3. Django~urls.py---&gt;views.py
  4. nginx配合modsecurity实现WAF功能
  5. Visual Studio Code asp.net 5环境搭建技能Get
  6. Oracle Gateways透明网关访问SQL Server
  7. hihocoder 1310 岛屿
  8. java08双重循环打印图形
  9. 【转】C++动态创建二维数组,二维数组指针
  10. 【c语言】调整数组使奇数所有都位于偶数前面
  11. javascript高级程序设计第3版——第1Java章 DOM扩展
  12. Oracle实战笔记(第一天)
  13. CLR via c# 值类型“不可变”
  14. 洛谷P2764 最小路径覆盖问题
  15. kvm虚拟化管理平台WebVirtMgr部署-完整记录(3)
  16. python---面对对象的组合
  17. 2017面向对象程序设计(Java) 第4周学习指导及要求(2017.9.14-2017.9.18)
  18. Vue 嵌套数组 数组更新视图不更新
  19. 002 Jupyter-NoteBook工具介绍(网页版编辑器)
  20. python2安装pymongo

热门文章

  1. openstack trove 数据库镜像构建列表
  2. Html 常见标签,css基础样式,css的浮动和清流,浏览器的兼容
  3. 学生选课系统(Java语言期末前测试)
  4. POJ 1979:Red and Black
  5. Hadoop的常用指令
  6. linux常用命令及小知识点
  7. IPC---有名管道FIFO
  8. eclipse使用jetty服务器
  9. 第04项目:淘淘商城(SpringMVC+Spring+Mybatis) 的学习实践总结【第二天】
  10. JAVA--Mybatis-Spring-SpringMVC框架整合