Time Limit: 2 sec / Memory Limit: 256 MB
Score : 400400 points
There are NN cities. There are also KK roads and LL railways, extending between the cities. The ii-th road bidirectionally connects the pipi-th and qiqi-th cities, and the ii-th railway bidirectionally connects the riri-th and sisi-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 AA and BB are connected by roads if city BB is reachable from city AA 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.
The input is given from Standard Input in the following format:
NN KK LL p1p1 q1q1 : pKpK qKqK r1r1 s1s1 : rLrL sLsLPrint NN integers. The ii-th of them should represent the number of the cities connected to the ii-th city by both roads and railways.
Copy
4 3 1 1 2 2 3 3 4 2 3Copy
1 2 2 1All the four cities are connected to each other by roads.
By railways, only the second and third cities are connected. Thus, the answers for the cities are 1,2,21,2,2 and 11, respectively.
Copy
4 2 2 1 2 2 3 1 4 2 3Copy
1 2 2 1Copy
7 4 4 1 2 2 3 2 5 6 7 3 5 4 5 3 4 6 7Copy
1 1 2 1 2 2 2N个点,K条A型边,L条B型边,问每个点与多少点“相连”,
此处相连指既可以通过纯A型边相连,也可以通过纯B型边相连。
可以根据两种不同的边划分两种联通块(并查集,dfs都可以),
然后一个点如果和另一个点相通,那个他两个一定属于相同的联通块
(2种联通快均是),所以,对于每一个点,我们可以用两个联通快标
号组成的数对来代表该点,然后只需要输出每个点对应数对的value即
可,数对可以用map存储,数对作为key,对应点数为value。