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