UVALive 6910 Cutting Tree 并查集
Cutting Tree题目连接：
https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=4922
Description
Tree in graph theory refers to any connected graph (of nodes and edges) which has no simple cycle,
while forest corresponds to a collection of one or more trees. In this problem, you are given a forest of
N nodes (of rooted trees) and K queries. Each query is in the form of:
· C x : remove the edge connecting node and its parent. If node has no parent, then ignore this
query.
· Q a b : output ‘YES’ if there is a path from node to node in the forest; otherwise, ‘NO’.
For example, let the initial forest is shown by Figure 1.
Figure 1. Figure 2.
Let’s consider the following queries (in order):
[*]Q 5 7 : output YES.
[*]C 2 : remove edge (2, 1) — the resulting forest is shown in Figure 2.
[*]Q 5 7 : output NO, as there is no path from node 5 to node 7 in Figure 2.
[*]Q 4 6 : output YES.
Input
The first line of input contains an integer T (T ≤ 50) denoting the number of cases. Each case begins
with two integers: N and K (1 ≤ N ≤ 20, 000; 1 ≤ K ≤ 5, 000) denoting the number of nodes in the
forest and the number of queries respectively. The nodes are numbered from 1 to N. The next line
contains N integers Pi (0 ≤ Pi ≤ N) denoting the parent of i-th node respectively. Pi = 0 means that
node i does not have any parent (i.e. it’s a root of a tree). You are guaranteed that the given input
corresponds to a valid forest. The next K lines represent the queries. Each query is in the form of ‘C
x’ or ‘Q a b’ (1 ≤ x, a, b ≤ N), as described in the problem statement above
Output
For each case, output ‘Case #X:’ in a line, where X is the case number starts from 1. For each ‘Q
a b’ query in the input, output either ‘YES’ or ‘NO’ (without quotes) in a line whether there is a path
from node a to node b in the forest.
Explanation for 2nd sample case:
The initial forest is shown in Figure 3 below.
[*]C 3 : remove edge (3, 2) — the resulting forest is shown in Figure 4.
[*]Q 1 2 : output YES.
[*]C 1 : remove edge (1, 2) — the resulting forest is shown in Figure 5.
[*]Q 1 2 : output NO as there is no path from node 1 to node 2 in Figure 5
Sample Input
4
7 4
0 1 1 2 2 2 3
Q 5 7
C 2
Q 5 7
Q 4 6
4 4
2 0 2 3
C 3
Q 1 2
C 1
Q 1 2
3 5
0 3 0
C 1
Q 1 2
C 3
C 1
Q 2 3
1 1
0
Q 1 1
Sample Output
Case #1:
YES
NO
YES
Case #2:
YES
NO
Case #3:
NO
YES
Case #4:
YES
Hint
题意
给你个森林，俩操作，1是砍掉与他父亲的连边，2是查询xy是否在同一个连通块里面
题解：
倒着做，砍边就变成连边了，然后并茶几莽一波就好了
代码
#include<bits/stdc++.h>
using namespace std;
const int maxn = 2e4+7;
int cas = 0;
int fa;
int e;
int flag;
int a,b,c;;
int fi(int x){
if(x==fa)return x;
return fa=fi(fa);
}
void init(){
memset(flag,0,sizeof(flag));
}
void solve(){
init();
vector<int>ans;
int n,m;
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
fa=i;
for(int i=1;i<=n;i++)
scanf("%d",&e);
for(int i=1;i<=m;i++){
string s;cin>>s;
if(s=='C'){
a=1;
scanf("%d",&b);
flag]++;
}else{
a=0;
scanf("%d%d",&b,&c);
}
}
for(int i=1;i<=n;i++){
if(flag==0&&e!=0){
fa=fi(e);
}
}
for(int i=m;i>=1;i--){
if(a==1){
flag]--;
if(flag]==0&&e]!=0)
fa)]=fi(e]);
}else{
if(fi(b)==fi(c))ans.push_back(1);
else ans.push_back(0);
}
}
for(int i=ans.size()-1;i>=0;i--){
if(ans)printf("YES\n");
else printf("NO\n");
}
}
int main(){
//freopen("1.txt","r",stdin);
int t;
scanf("%d",&t);
while(t--){
printf("Case #%d:\n",++cas);
solve();
}
return 0;
}
文档来源：51CTO技术博客https://blog.51cto.com/u_15303184/3108577
页:
[1]