P7928

rt，题解都是并查集，但是我在打暴力的时候发现只要循环暴力 100 遍就可以直接过。

#include<bits/stdc++.h>
#define arrout(a,n) rep(i,1,n)std::cout<<a[i]<<" "
#define arrin(a,n) rep(i,1,n)std::cin>>a[i]
#define rep(i,x,n) for(int i=x;i<=n;i++)
#define dep(i,x,n) for(int i=x;i>=n;i--)
#define erg(i,x) for(int i=head[x];i;i=e[i].nex)
#define dbg(x) std::cout<<#x<<":"<<x<<" "
#define mem(a,x) memset(a,x,sizeof a)
#define all(x) x.begin(),x.end()
#define arrall(a,n) a+1,a+1+n
#define PII std::pair<int,int>
#define m_p std::make_pair
#define u_b upper_bound
#define l_b lower_bound
#define p_b push_back
#define CD const double
#define CI const int
#define int long long
#define il inline
#define ss second
#define ff first
#define itn int
CI N=1e5+5;
std::unordered_map<std::string,int> vis;
std::unordered_map<int,int> mp;
int n,cnt,a[N],b[N];
signed main() {
    std::cin>>n;
    rep(i,1,n) {
        std::string s;
        std::cin>>s;
        if(s[0]>='0'&&s[0]<='9') {
            a[i]=atoi(s.c_str());
        } else {
            a[i]=1000+(!vis[s]?vis[s]=++cnt:vis[s]);
        }
    }
    rep(i,1,n) {
        std::string s;
        std::cin>>s;
        if(s[0]>='0'&&s[0]<='9') {
            b[i]=atoi(s.c_str());
        } else {
            b[i]=1000+(!vis[s]?vis[s]=++cnt:vis[s]);
        }
    }
    int t=100;
    while(t--) {//重复100次
        rep(i,1,n) {
            if(a[i]>1000&&b[i]>1000) {
                if(mp[a[i]]) {
                    a[i]=mp[a[i]];
                    if(!mp[b[i]]) {
                        mp[b[i]]=a[i];
                        b[i]=a[i];
                    }
                }
                if(mp[b[i]]) {
                    b[i]=mp[b[i]];
                    if(!mp[a[i]]) {
                        mp[a[i]]=b[i];
                        a[i]=b[i];
                    }
                }
            }
            if(a[i]>1000&&b[i]<=1000) {
                if(!mp[a[i]]) {
                    mp[a[i]]=b[i];
                    a[i]=b[i];
                } else if(mp[a[i]]!=b[i]) {
                    puts("NE");
                    exit(0);
                }
            }
            if(b[i]>1000&&a[i]<=1000) {
                if(!mp[b[i]]) {
                    mp[b[i]]=a[i];
                    b[i]=a[i];
                } else if(mp[b[i]]!=a[i]) {
                    puts("NE");
                    exit(0);
                }
            }
        }
        rep(i,1,n) {
            if(mp[a[i]]!=0&&a[i]>1000) {
                a[i]=mp[a[i]];
            }
            if(mp[b[i]]!=0&&b[i]>1000) {
                b[i]=mp[b[i]];
            }
            if(b[i]!=a[i]&&a[i]<=1000&&b[i]<=1000) {
                puts("NE");
                exit(0);
            }
        }
    }
    puts("DA");
    // arrout(a,n);
    // puts("");
    // arrout(b,n);
    return 0;
}