编程介的小学生 2017-02-12 12:42 采纳率: 20.5%
浏览 934
已采纳

Graph of Black and White

问题描述 :

Once upon a time, there was a graph. Actually, it was an undirected forest, i.e., an undirected graph without circles. There were N nodes in this forest, numbered from 1 to N inclusively, with each node colored black or white. Elves had been living in the forest for many years. Their homes were inside the nodes, and sometimes they would move their homes or visit other elves living in another node. However, they could only move between nodes that were connected by an edge or a path formed by several end-to-end connected edges. In other words, they could only move in the same tree. If two nodes were not connected, the elves could not travel between them. When they were passing a node, including the starting and the ending ones, they should use black or white magic power according to the color of the node. Waste is criminal, so during a journey the elves never pass a node twice.

The structure of the forest might change, when no elves were travelling. Two disconnected nodes might be connected by a new edge between them, or an existing edge might disappear, or the color of a node might change. Anyway, there would never be circles in the forest, so the forest remained a forest. THUS HARMONY LONG LASTS!

Elves were intelligent. They knew everything happening in the forest. And they knew how much black and white magic power was used when they travel. Why? Because YY, the most intelligent one elf, simulated everything and told them.

输入:

Input contains several test cases.

For each test case, the first line contains two positive integers, N (N ≤ 10000) and M (M ≤ 100000), indicating the number of nodes in the graph and the number of operations that YY should simulate. At the beginning of his simulation, there were not any edge in the forest.

The following lines contains N space separated characters, each being ‘B’ or ‘W’ (quotes for clarity), the ith of which indicates the color of the node numbered i, black or white.

M lines follow, indicating the M operations to simulate. For each line, it will be one of the four types:

add u v
The two nodes numbered u and v (1≤u, v≤N, and u≠v) are connected by a new edge. It is guaranteed that these two nodes are not connected before this operation.

del u v
The edge between the two nodes numbered u and v (1≤u, v≤N, and u≠v) disappears. It is guaranteed that this edge exists before this operation.

set u c
The color of the node numbered u (1≤u≤N) is set to c (c=’B’ or ‘W’, quotes for clarity).

query u v
Now YY tells the elves the number of black and white nodes that have to be passed when travelling between nodes numbered u and v (1≤u, v≤N) inclusively, or tells them the journey is impossible.

Input ends with N=M=0.

输出:

Input contains several test cases.

For each test case, the first line contains two positive integers, N (N ≤ 10000) and M (M ≤ 100000), indicating the number of nodes in the graph and the number of operations that YY should simulate. At the beginning of his simulation, there were not any edge in the forest.

The following lines contains N space separated characters, each being ‘B’ or ‘W’ (quotes for clarity), the ith of which indicates the color of the node numbered i, black or white.

M lines follow, indicating the M operations to simulate. For each line, it will be one of the four types:

add u v
The two nodes numbered u and v (1≤u, v≤N, and u≠v) are connected by a new edge. It is guaranteed that these two nodes are not connected before this operation.

del u v
The edge between the two nodes numbered u and v (1≤u, v≤N, and u≠v) disappears. It is guaranteed that this edge exists before this operation.

set u c
The color of the node numbered u (1≤u≤N) is set to c (c=’B’ or ‘W’, quotes for clarity).

query u v
Now YY tells the elves the number of black and white nodes that have to be passed when travelling between nodes numbered u and v (1≤u, v≤N) inclusively, or tells them the journey is impossible.

Input ends with N=M=0.

样例输入:

3 8
B W B
query 1 2
add 1 2
add 2 3
query 1 3
del 2 3
add 1 3
set 1 W
query 3 2
0 0
样例输出:

-1
2 1
1 2

  • 写回答

1条回答 默认 最新

  • threenewbee 2017-02-17 20:52
    关注
    本回答被题主选为最佳回答 , 对您是否有帮助呢?
    评论

报告相同问题?

悬赏问题

  • ¥15 寻一个支付宝扫码远程授权登录的软件助手app
  • ¥15 解riccati方程组
  • ¥15 display:none;样式在嵌套结构中的已设置了display样式的元素上不起作用?
  • ¥30 用arduino开发esp32控制ps2手柄一直报错
  • ¥15 使用rabbitMQ 消息队列作为url源进行多线程爬取时,总有几个url没有处理的问题。
  • ¥15 Ubuntu在安装序列比对软件STAR时出现报错如何解决
  • ¥50 树莓派安卓APK系统签名
  • ¥65 汇编语言除法溢出问题
  • ¥15 Visual Studio问题
  • ¥20 求一个html代码,有偿