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*10
5
1≤K,L≤10
5
1≤pi,qi,ri,si≤N
pi<qi
ri<si
When i≠j,(pi,qi)≠(pj,qj)
When i≠j,(ri,si)≠(rj,sj)
Connectivity
发布时间:2020-12-14 04:49:37 所属栏目:大数据 来源:网络整理
导读:题目描述 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
题目描述输入
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
提示All the four cities are connected to each other by roads.
嘤语阅读理解.....刚开始读了半天没读懂
即能同时只通过火车和公路连到该城市的城市个数,自己算一个.....
即两个并查集的交集,并查集不难,注意要路径压缩,不然T
用struct写并查集
然后pair表示连接的道路和铁路的根节点
#include <bits/stdc++.h> #define ll long long using namespace std; const int maxn=2e5+7; #define p make_pair map<pair<int,int>,int>mp; int sa[maxn],sb[maxn],a1,a2; struct dsu { int fa[maxn]; void unit(int n){ for(int i=1;i<=n;i++){ fa[i]=i; } } int findset(int a){ if(fa[a]==a) { return a; } return fa[a]=findset(fa[a]); } void union_(int x,int y){ a1=findset(x); a2=findset(y); if(a1!=a2){ fa[a1]=a2; } } }; int main() { int n,k,l,a,b; scanf("%d %d %d",&n,&k,&l); dsu s1,s2; s1.unit(n); s2.unit(n); for(int i=1;i<=k;i++){ scanf("%d %d",&a,&b); s1.union_(a,b); } for(int i=1;i<=l;i++){ scanf("%d %d",&b); s2.union_(a,b); } for(int i=1;i<=n;i++){ sa[i]=s1.findset(i); sb[i]=s2.findset(i); mp[p(sa[i],sb[i])]++; } for(int i=1;i<=n;i++){ if(i!=1) printf(" "); printf("%d",mp[p(sa[i],sb[i])]); } printf("n"); return 0; } (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |