2022/7/14

Split Into Two Sets  Type and search

Type and search   Algorithm learning notes (4)—— Type and search | FZSF (gitee.io)

         Consider the general situation , If there is at least one number x Finally, it appears twice in a set , Then it must not . Take the second set of examples in the title for example , Numbers appear 1 Yes, there is 1 Second input and second 3 Time input , Numbers appear 2 Yes, there is 1 Time and number 5 Time , Numbers appear 3 Yes, there is 3 Time and number 5 Time , You can find the 5 The second input is the 5 No matter how many dominoes are put, they don't meet the conditions , This judgment can be made by category and search set , Numbers appear 1 There are 1 and 3, be 1 and 3 Can't be in a set , therefore 1,3 It's the enemy ,1 and 3 The enemy of 3+n It's a kind of ,3 and 1 The enemy of 1+n It's a kind of , Then the number appears 2 There are 3 and 5, be 3 and 5 It's the enemy ,3 and 5 The enemy of 5+n It's a kind of ,5 and 3 The enemy of 3+n It's a kind of , Numbers appear 3 There are 1 and 5, be 1 and 5 It's the enemy , because 1 and 5 All are 3 The enemy of , The enemy of the enemy is a friend ,1 and 5 adopt 3 Established a connection , So it doesn't meet the conditions

E. Split Into Two Sets（ Type and search ）（Codeforces Round #805 (Div. 3)）_FAUX123455 The blog of -CSDN Blog

#include <bits/stdc++.h>
#define ll long long
#define lowbit(x) ((x)&(-x))
using namespace std;
const ll mod=998244353;
ll t,n,s[500005];
vector<ll>v[200005];
struct node{
    ll a,b;
}p[200005];
ll findd(ll x){
    return x==s[x]?x:s[x]=findd(s[x]);
}
void uni(ll x,ll y){
    ll xx=findd(x),yy=findd(y);
    if(xx!=yy) s[xx]=yy;
}
int main(){
    scanf("%lld",&t);
    while(t--){
        scanf("%lld",&n);
        for(int i=1;i<=n;i++) v[i].clear(),s[i]=i,s[i+n]=i+n;
        for(int i=1;i<=n;i++){
            ll a,b;
            scanf("%lld%lld",&a,&b);
            v[a].push_back(i);
            v[b].push_back(i);
        }
        ll flag=1,cnt=0;
        for(int i=1;i<=n;i++){
            if(v[i].size()==2){
                p[++cnt].a=v[i][0];
                p[cnt].b=v[i][1];
            }
            else if(v[i].size()>2) flag=0;
        }
        for(int i=1;i<=cnt;i++){
            if(findd(p[i].a)==findd(p[i].b)){
                flag=0;break;
            }
            uni(p[i].a,p[i].b+n);
            uni(p[i].b,p[i].a+n);
        }
        if(flag) printf("Yes\n");
        else printf("No\n");
    }
    return 0;
}

P1525 [NOIP2010 Improvement group ] Detain criminals - Luogu | New ecology of computer science education (luogu.com.cn) Type and search

The topic is to make the output as small as possible , So we sort from big to small , From the beginning of the great influence, they will be divided into different cells , Until I can't arrange , At this time, the impact of this pair is the smallest

Type and search _Linda_yezi_coder The blog of -CSDN Blog _ Type and search

#include <bits/stdc++.h>
#define ll long long
#define lowbit(x) ((x)&(-x))
using namespace std;
const ll mod=998244353;
ll n,m,s[500005];
struct node{
    ll a,b,c;
    bool operator<(const node d)const{
        return c>d.c;
    }
}p[200005];
ll findd(ll x){
    return x==s[x]?x:s[x]=findd(s[x]);
}
void uni(ll x,ll y){
    ll xx=findd(x),yy=findd(y);
    if(xx!=yy) s[xx]=yy;
}
int main(){
    scanf("%lld%lld",&n,&m);
    for(int i=1;i<=m;i++) scanf("%lld%lld%lld",&p[i].a,&p[i].b,&p[i].c);
    sort(p+1,p+m+1);
    for(int i=1;i<=n;i++) s[i]=i,s[i+n]=i+n;
    for(int i=1;i<=m;i++){
        if(findd(p[i].a)==findd(p[i].b)){
            printf("%lld\n",p[i].c);return 0;
        }
        uni(p[i].a,p[i].b+n);
        uni(p[i].b,p[i].a+n);
    }
    printf("0\n");
    return 0;
}

P3958 [NOIP2017 Improvement group ] cheese - Luogu | New ecology of computer science education (luogu.com.cn)

Last time I did this problem, I used dfs Written , Maybe it's not my own idea , This time I wrote it with my own collection , In fact, it is also relatively simple , If two cheese holes are interconnected , It shows that these two are related , Establish the same relationship between the lower surface and the upper surface , Finally, just look at whether the lower surface is related to the upper surface

#include <bits/stdc++.h>
#define ll long long
#define lowbit(x) ((x)&(-x))
using namespace std;
const ll mod=998244353;
ll t,n,s[1005];
double h,r;
struct node{
    double x,y,z;
}p[1005];
bool pd(node a,node b){
    double dist=sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y)+(a.z-b.z)*(a.z-b.z));
    return dist<=2*r;
}
ll findd(ll x){
    return x==s[x]?x:s[x]=findd(s[x]);
}
void uni(ll x,ll y){
    ll xx=findd(x),yy=findd(y);
    if(xx!=yy) s[xx]=yy;
}
int main(){
    scanf("%lld",&t);
    while(t--){
        scanf("%lld%lf%lf",&n,&h,&r);
        for(int i=1;i<=n;i++) scanf("%lf%lf%lf",&p[i].x,&p[i].y,&p[i].z);
        for(int i=0;i<=n+1;i++) s[i]=i;
        for(int i=1;i<=n;i++){
            if(p[i].z<=r) uni(i,0);
            if(h-p[i].z<=r) uni(i,n+1);
        }
        for(int i=1;i<=n;i++){
            for(int j=i+1;j<=n;j++){
                if(pd(p[i],p[j])) uni(i,j);
            }
        }
        //for(int i=0;i<=n+1;i++) cout<<findd(i)<<" "<<i<<endl;
        if(findd(0)==findd(n+1)) printf("Yes\n");
        else printf("No\n");
    }
    return 0;
}

P2661 [NOIP2015 Improvement group ] Information transmission - Luogu | New ecology of computer science education (luogu.com.cn) Union checking set

Let this question stumble again , Read the solution for a long time , The idea is to find the smallest link , Let's talk about the previous practice , If both numbers have the same ancestor , Then the length of the ring is the sum of the length of two numbers reaching the ancestor and 1

#include <bits/stdc++.h>
#define ll long long
#define lowbit(x) ((x)&(-x))
using namespace std;
const ll mod=998244353;
ll n,s[200005],d[200005],t[200005],ans;
ll findd(ll x){
    if(x!=s[x]){
        ll tmp=s[x];
        s[x]=findd(s[x]);
        d[x]+=d[tmp];// The original length plus the updated length 
    }
    return s[x];
}
void uni(ll x,ll y){
    ll xx=findd(x),yy=findd(y);
    if(xx!=yy) s[xx]=yy,d[x]=d[y]+1;
    else ans=min(ans,d[y]+d[x]+1);// Actually d[y]+1 Can , because x Is the initial root node ,d[x] It must be 0
}
int main(){
    scanf("%lld",&n);
    ans=1e18;
    for(int i=1;i<=n;i++) s[i]=i,d[i]=0;
    for(int i=1;i<=n;i++){
        scanf("%lld",&t[i]);
            uni(i,t[i]);
    }
    printf("%lld\n",ans);
    return 0;
}

        In fact, there is a simple way to understand , My thinking is similar to this , But I didn't do it , It may be that the path cannot be compressed , Although path compression saves time, the process will be lost , Do not use path compression cnt Record how many steps it took to reach the root node , So this one cnt Is the length of the ring , In addition, there are some points that should be paid attention to in this problem , Every time you start from i->t[i] Merged like this , This is in line with the meaning of the topic , And easy to understand

#include <bits/stdc++.h>
#define ll long long
#define lowbit(x) ((x)&(-x))
using namespace std;
const ll mod=998244353;
ll n,s[200005],d[200005],t[200005],cnt;
ll findd(ll x){
    cnt++;
    return x==s[x]?x:findd(s[x]);
}
void uni(ll x,ll y){
    ll xx=findd(x),yy=findd(y);
    if(xx!=yy) s[xx]=yy,d[yy]++;
}
int main(){
    scanf("%lld",&n);
    ll ans=1e18;
    for(int i=1;i<=n;i++) s[i]=i,d[i]=0;
    for(int i=1;i<=n;i++){
        scanf("%lld",&t[i]);
        cnt=0;
        if(i==findd(t[i])){
            ans=min(ans,cnt);
        }
        else{
            s[i]=t[i];
        }
    }
    printf("%lld\n",ans);
    return 0;
}