parallelism set expansion
ordinary parallel set (math.)
Example.
1.Rock Valley P1197 Star Wars
Link.
[P1197 JSOI2008] Star Wars - Rock Valley | The New Ecology of Computer Science Education ()
Type.
Ordinary concatenated set + reverse addition
Analysis.
It is very difficult to delete edges positively, consider the reverse solution, first find the number of connected blocks after deleting all the required points, and then add them one by one to simplify the problem.
Code.
const int N = 400005;
struct edges{
int v,ne;
}e[N << 1];
int h[N],idx = 0;
void add(int u,int v){
e[idx] = {v,h[u]};
h[u] = idx++;
}
int f[N];
int fd(int x){
if(x==f[x]) return x;
return f[x] = fd(f[x]);
}
int vis[N],ans[N];
int n,m;
void solve(){
memset(h,-1,sizeof h);
cin >> n >> m;
for(int i = 1;i<=n;i++) f[i] = i;
vector<int> b;
for(int i = 1;i<=m;i++){
int u,v;
cin >> u >> v;
u++,v++;
add(v,u);
add(u,v);
}
int k;
cin >> k;
int res = n - k;
for(int i = 0;i<k;i++){
int t;
cin >> t;
t++;
vis[t] = 1;
b.push_back(t);
}
for(int i = 1;i<=n;i++){
if(vis[i]) continue;
for(int j = h[i];~j;j=e[j].ne){
int v = e[j].v;
if(vis[v]) continue;
if(f[fd(i)] != f[fd(v)]){
res--;
f[fd(i)] = f[fd(v)];
}
}
}
ans[k+1] = res;
for(int i = k - 1;i >= 0;i--){
vis[b[i]] = 0;
res++;
for(int j = h[b[i]];~j;j=e[j].ne){
int v = e[j].v;
if(vis[v]) continue;
if(f[fd(b[i])] != f[fd(v)]){
res--;
f[fd(b[i])] = f[fd(v)];
}
}
ans[i + 1] = res;
}
for(int i = 1;i<=k+1;i++){
cout << ans[i] << endl;
}
}
2. Rockwell P1955 Program Automation Analysis
Link.
[P1955 NOI2015] Automated Program Analysis - Rock Valley | The New Ecology of Computer Science Education ()
Type.
Ordinary parallel sets + discretization
Analysis.
Ordinary parallel check set to determine whether the contradiction, large data discretization
Code.
const int N = 200005;
struct DSU {
vector<int> f;
DSU(){}
DSU(int n) {
init(n);
}
void init(int n) {
(n);
iota((), (), 0);
}
int fd(int x) {
if(f[x]==x) return x;
return f[x] = fd(f[x]);
}
bool same(int x, int y) {
return fd(x) == fd(y);
}
bool mg(int x, int y) {
x = fd(x);
y = fd(y);
if (x == y)return false;
f[y] = x;
return true;
}
};
int gt_idx(vector<int>& a,int i){
int t = lower_bound((),(),i) - () + 1;
return t;
}
void solve(){
int n;
cin >> n;
vector<int> v1;
vector<pair<int,int>> ys;
vector<pair<int,int>> ns;
vector<int> a;
for(int i = 0;i < n;i++){
int u,v,op;
cin >> u >> v >> op;
if(op==1){
ys.push_back({u,v});
}else{
ns.push_back({u,v});
}
a.push_back(u);
a.push_back(v);
}
sort((),());
(unique((),()),());
int sz = ();
DSU d(sz + 1);
for(auto &[u,v]:ys){
(gt_idx(a,u),gt_idx(a,v));
}
for(auto &[u,v]:ns){
if((gt_idx(a,u)) == (gt_idx(a,v))){
cout << "NO" << endl;
return;
}
}
cout << "YES" << endl;
}
weighted parallel set (math.)
Example.
1. Rock Valley P2024 Food Chain
Link.
[P2024 NOI2001] Food Chain - Rock Valley | The New Ecology of Computer Science Education ()
Type.
weighted parallel set (math.)
Analysis.
Maintain %3 relations, consider merging when maintaining set relations, in the same kind of time d[u] - d[v] in the sense of %3 must be 0, x eats y then must be 1, the topic does not need to consider the case of 2, because there is no set y eats x correctly
Code.
const int N = 200005;
int f[N],d[N];
int n,m;
int fd(int x){
if(x!=f[x]){
int t = f[x];
f[x] = fd(f[x]);
d[x] += d[t];
}
return f[x];
}
int calc(int x,int y){
return ((x-y)%3 + 3)%3;
}
void merge(int x,int y,int v){
int px = fd(x),py = fd(y);
f[px] = py;
d[px] = d[y] - d[x] + v;
}
void solve(){
cin >> n >> m;
iota(f,f+n+1,0);
int cnt = 0;
while(m--){
int u,v,op;
cin >> op >> u >> v;
if(u>n||v>n){
cnt++;
continue;
}
if(op==1){
if(fd(u)==fd(v) && calc(d[u],d[v]) != 0){
cnt++;
continue;
}
//d[v] = d[u] + d[fd(u)]
//d[fd[u]] = d[v] - d[u]
if(fd(u)!=fd(v)) merge(u,v,0);
}else{
if(fd(u)==fd(v) && calc(d[u],d[v]) != 1){
cnt++;
continue;
}
//d[v] = d[u] - 1 + d[fd(u)]
//d[fd[u]] = d[v] - d[u] + 1
if(fd(u)!=fd(v)) merge(u,v,1);
}
}
cout << cnt << endl;
}
2. Logu P1196 Legend of the Galactic Heroes
Link.
[P1196 NOI2002] Legend of the Galactic Heroes - Rock Valley | New Ecology of Computer Science Education ()
Type.
weighted parallel set (math.)
Analysis.
Maintain two variables, one for the size of the set and one for the distance from the element to the root, and then manipulate it.
Code.
const int N = 200005;
int sz[N],d[N],f[N];
void init(){
for(int i = 0; i < N - 1;i++){
f[i] = i;
sz[i] = 1;
}
}
int fd(int x){
if(f[x]!=x){
int t = f[x];
f[x] = fd(f[x]);
d[x] += d[t];
}
return f[x];
}
void merge(int x,int y){
int px = fd(x),py = fd(y);
f[px] = py;
d[px] = sz[py];
sz[py] += sz[px];
}
void solve(){
int q;
init();
cin >> q;
while(q--){
int x,y;
char op;
cin >> op >>x >> y;
if(op=='C'){
if(fd(x)!=fd(y)){
cout <<-1<<endl;
}else{
cout << abs(d[x]-d[y]) - 1 << endl;
}
}else{
merge(x,y);
}
}
}
3. Rock Valley P5937 Parity Game
Link.
[P5937 CEOI1999] Parity Game - Rock Valley | New Ecology of Computer Science Education ()
Type.
weighted parallel set (math.)
Analysis.
Prefix and sum, combine y and x - 1 to determine parity.
Code.
const int N = 200005;
int n,q;
int idx = 0;
map<int,int> h;
int gt(int x){
if((x)) return h[x];
h[x] = ++idx;
return idx;
}
int d[N],f[N];
int fd(int x){
if(f[x] != x){
int t = f[x];
f[x] = fd(f[x]);
d[x] += d[t];
}
return f[x];
}
void merge(int x,int y,int v){
int px = fd(x),py = fd(y);
f[px] = py;
d[px] = d[y] - d[x] + v;
}
int calc(int x,int y){
return ((d[x] - d[y])%2 + 2)%2;
}
void solve(){
cin >> n >> q;
int res = q;
for(int i = 0;i<N;i++) f[i] = i;
int id = 0;
while(q--){
int x,y;
++id;
string op;
cin >> x >> y >> op;
if(x==y&&op=="even"){
res = id-1;
break;
}
x = gt(x - 1);
y = gt(y);
if(op=="even"){
if(fd(x)==fd(y)){
if(calc(x,y) == 1){
res = id - 1;
break;
}
}else{
merge(x,y,0);
}
}else{
if(fd(x)==fd(y)){
if(calc(x,y) == 0){
res = id - 1;
break;
}
}else{
merge(x,y,1);
}
}
}
cout << res << endl;
}
Extended domain parallelism set
Example.
1. Rock Valley P1525 Criminal detention
Link.
[P1525 NOIP2010 Improvement Group] Criminal Detention - Laguna | New Ecology of Computer Science Education ()
Type.
Extended domain parallelism set + weighted parallelism set
Analysis.
Method 1 (Extended Domain Concatenation Set).
- Two sets, sorted from largest to smallest, consider the hostile two people into two sets, and extend the domain merge, the enemy of the enemy is a friend, that is, set x has two enemies y z, then z and x + n to build edges, x + n and y to build edges, through x + n this virtual point to connect should be in a set of y and z, if in the same set, and is hostile, then direct output can be
Method II (weighted parallelism set).
- sorted from largest to smallest, to avoid the previous number in a *, the two sets will be merged, and assigned a value of 1 on behalf of the two numbers are not in the same *, so in the back we can judge, if the two numbers have been merged before and mod operation bit 0 on behalf of the two sets must be in a *, then the direct output of w, (Otherwise, w will be larger)
Code.
Method I.
int n,m;
struct qs{
int u,v,w;
bool operator<(const qs& q1)const{
return w > ;
}
};
struct DSU {
vector<int> f, sz;
DSU(){}
DSU(int n) {
init(n);
}
void init(int n) {
(n);
iota((), (), 0);
(n, 1);
}
int fd(int x) {
if(f[x]==x) return x;
return f[x] = fd(f[x]);
}
bool mg(int x, int y) {
x = fd(x);
y = fd(y);
if (x == y)return false;
f[y] = x;
return true;
}
};
void solve(){
cin >> n >> m;
DSU d(2*(n+1));
vector<qs> q;
for(int i = 0; i < m;i++){
int u,v,w;
cin >> u >> v >> w;
q.push_back({u,v,w});
}
sort((),());
for(int i = 0;i < ();i++){
int u = q[i].u,v = q[i].v,w = q[i].w;
if((u) == (v)){
cout << w <<endl;
return;
}
(u,v+n);
(u+n,v);
}
cout << 0 << endl;
}
Method II.
struct qs
{
int u,v,w;
bool operator<(const qs &t)const{return w > ;};
};
int f[N],d[N];
int n,m;
int fd(int x){
if(x!=f[x]){
int t = f[x];
f[x] = fd(f[x]);
d[x] += d[t];
}
return f[x];
}
int calc(int x,int y){
return ((x-y)%2 + 2)%2;
}
void merge(int x,int y){
int px = fd(x),py = fd(y);
f[px] = py;
d[px] = d[y] - d[x] + 1;
}
void solve(){
cin >> n >> m;
int q = m;
vector<qs> a;
iota(f,f+n+1,0);
while(q--){
int u,v,w;
cin >> u >> v >> w;
a.push_back({u,v,w});
}
sort((),());
for(int i = 0; i < m;i++){
int u = a[i].u,v = a[i].v,w = a[i].w;
if(fd(u)==fd(v)){
if(calc(d[u],d[v]) == 0){
cout << w << endl;
return;
}
}else{
merge(u,v);
}
}
cout << 0 <<endl;
}