6492: Connectivity

时间限制: 1 Sec  内存限制: 128 MB
提交: 118  解决: 28
[提交][状态][讨论版][命题人:admin]

题目描述

There are N cities. There are also K roads and L railways, extending between the cities. The i-th road bidirectionally connects the pi-th and qi-th cities, and the i-th railway bidirectionally connects the ri-th and si-th cities. No two roads connect the same pair of cities. Similarly, no two railways connect the same pair of cities.
We will say city A and B are connected by roads if city B is reachable from city A by traversing some number of roads. Here, any city is considered to be connected to itself by roads. We will also define connectivity by railways similarly.
For each city, find the number of the cities connected to that city by both roads and railways.

Constraints
2≤N≤2*105
1≤K,L≤105
1≤pi,qi,ri,si≤N
pi<qi
ri<si
When i≠j, (pi,qi)≠(pj,qj)
When i≠j, (ri,si)≠(rj,sj)

输入

The input is given from Standard Input in the following format:
N K L
p1 q1
:
pK qK
r1 s1
:
rL sL

输出

Print N integers. The i-th of them should represent the number of the cities connected to the i-th city by both roads and railways.

样例输入

4 3 1

1 2

2 3

3 4

2 3

样例输出

1 2 2 1
统计两个并查集交集所含元素的个数，这个数就是交集中的每一个元素对应的答案（实际上是由每一个元素得到总的个数）
还有就是熟练掌握map和pair的用法，我就是知道思路但不知道怎么实现！
AC代码：

#include <bits/stdc++.h>
using namespace std;
const int maxn=2e5+100;
#define p make_pair
map<pair<int,int>,int>mapp;
int sa[maxn],sb[maxn];
struct record
{
int fa[maxn];
void unit(int n)
{
for(int i=1;i<=n;i++)
{
fa[i]=i;
}
}
int finding(int a)
{
if(fa[a]==a)
{
return a;
}
return fa[a]=finding(fa[a]);
}
void union_(int x,int y)
{
int b1=finding(x);
int b2=finding(y);
if(b1!=b2)
{
fa[b1]=b2;
}
}
};
int main()
{
int n,k,l,x,y;
scanf("%d %d %d",&n,&k,&l);
record s1,s2;
s1.unit(n);
s2.unit(n);
for(int i=1;i<=k;i++)
{
scanf("%d %d",&x,&y);
s1.union_(x,y);
}
for(int i=1;i<=l;i++)
{
scanf("%d %d",&x,&y);
s2.union_(x,y);
}
for(int i=1; i<=n; i++)
{
sa[i]=s1.finding(i);
sb[i]=s2.finding(i);
mapp[p(sa[i],sb[i])]++;
}
for(int i=1;i<=n;i++)
{
if(i==n)
{
printf("%d\n",mapp[p(sa[i],sb[i])]);
}
else
{
printf("%d ",mapp[p(sa[i],sb[i])]);
}
}
return 0;
}

最新文章

  1. c++转载系列 std::vector模板库用法介绍
  2. Spark基础知识汇总
  3. ubuntu su Authentication failure
  4. ASP.NET Web API 路由
  5. javascript 的默认对象
  6. fis-receiver：一行命令将项目部署到远程服务器
  7. Linux - gcc和g++的区别
  8. JavaScript开发之路02（Sencha Touch使用时常见问题及解决办法）
  9. android 添加左右滑屏手势
  10. LVS负载均衡中arp_ignore和arp_annonuce参数配置的含义
  11. Shell第三篇：基本语法
  12. [java语言]——InetAddress类的getByName()方法
  13. es head插件通过Nginx http basic 限制访问
  14. const成员函数用法
  15. javaScript之分支判断与内置对象
  16. 合作开发工具——freeze和pipreqs
  17. EF Core中DbContext可以被Dispose多次
  18. python正则表达式查找汉字
  19. Kettle 使用入门
  20. Android bp语法介绍

热门文章

  1. Pure CSS 的网格布局（比bootstrap小很多且易扩展的css UI）
  2. Scipy实现图片去噪
  3. excel常用函数之find，left，right，mid，len
  4. unity打包选项编辑器扩展
  5. poj3191(进制转换)
  6. django后台管理系统(admin)的简单使用
  7. 坑爹的 Java 可变参数，把我整得够惨。。
  8. MFS安装
  9. oracle view and MATERIALIZED VIEW
  10. falsk-sqlalchemy 连接数据库出现 No module named &#39;MySQLdb&#39;