-
暑假算法训练day7(并查集)
并查集过的比较顺利
A - 并查集
#include <bits/stdc++.h> using namespace std; const double pi = acos(-1.0); #define x first #define y second #define LL long long #define int LL #define pb push_back #define all(v) (v).begin(),(v).end() #define PII pair<int,int> #define ll_INF 0x7f7f7f7f7f7f7f7f #define INF 0x3f3f3f3f #define debug(x) cerr << #x << ": " << x << endl #define io ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr) LL Mod(LL a,LL mod){return (a%mod+mod)%mod;} LL lowbit(LL x){return x&-x;}//最低位1及其后面的0构成的数值 LL qmi(LL a,LL b,LL mod) {LL ans = 1; while(b){ if(b & 1) ans = ans * (a % mod) % mod; a = a % mod * (a % mod) % mod; b >>= 1;} return ans; } int _; int n,m; const int N=1e4+10; int f[N]; int find(int x) { if(x!=f[x])f[x]=find(f[x]); return f[x]; } void unite(int a,int b) { int x=find(a),y=find(b); if(x!=y)f[y]=x; } void init() { for(int i=0;i<=n;i++)f[i]=i; } void solve() { cin>>n>>m; init(); while(m--) { int z; cin>>z; if(z==1) { int x,y; cin>>x>>y; unite(x,y); } else { int x,y; cin>>x>>y; if(find(x)==find(y)) cout<<"Y"<<endl; else cout<<"N"<<endl; } } } signed main() { io; // cin>>_; // while(_--) solve(); return 0; }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
B - 家谱
#include <bits/stdc++.h> using namespace std; const double pi = acos(-1.0); #define x first #define y second #define LL long long #define int LL #define pb push_back #define all(v) (v).begin(),(v).end() #define PII pair<int,int> #define ll_INF 0x7f7f7f7f7f7f7f7f #define INF 0x3f3f3f3f #define debug(x) cerr << #x << ": " << x << endl #define io ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr) LL Mod(LL a,LL mod){return (a%mod+mod)%mod;} LL lowbit(LL x){return x&-x;}//最低位1及其后面的0构成的数值 LL qmi(LL a,LL b,LL mod) {LL ans = 1; while(b){ if(b & 1) ans = ans * (a % mod) % mod; a = a % mod * (a % mod) % mod; b >>= 1;} return ans; } int _; int n,m; const int N=1e5+10; int f[N]; map<string,int>mp1; map<int,string>mp2; int find(int x) { if(x!=f[x])f[x]=find(f[x]); return f[x]; } void unite(int x,int y) { int a=find(x),b=find(y); if(a!=b)f[b]=a; } void solve() { string s; string fa; int idx=1; for(int i=1;i<N;i++)f[i]=i; while(cin>>s,s!="$") { if(s[0]=='#') { s=s.substr(1); if(!mp1.count(s))mp1[s]=idx,mp2[idx]=s,idx++; fa=s; } else if(s[0]=='+') { s=s.substr(1); if(!mp1.count(s))mp1[s]=idx,mp2[idx]=s,idx++; unite(mp1[fa],mp1[s]); } else { s=s.substr(1); cout<<s<<' '<<mp2[find(mp1[s])]<<endl; } } } signed main() { io; // cin>>_; // while(_--) solve(); return 0; }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
C - 村村通
#include <bits/stdc++.h> using namespace std; const double pi = acos(-1.0); #define x first #define y second #define LL long long #define int LL #define pb push_back #define all(v) (v).begin(),(v).end() #define PII pair<int,int> #define ll_INF 0x7f7f7f7f7f7f7f7f #define INF 0x3f3f3f3f #define debug(x) cerr << #x << ": " << x << endl #define io ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr) LL Mod(LL a,LL mod){return (a%mod+mod)%mod;} LL lowbit(LL x){return x&-x;}//最低位1及其后面的0构成的数值 LL qmi(LL a,LL b,LL mod) {LL ans = 1; while(b){ if(b & 1) ans = ans * (a % mod) % mod; a = a % mod * (a % mod) % mod; b >>= 1;} return ans; } int _; int n,m; const int N=1010; int f[N]; int find(int x) { if(x!=f[x])f[x]=find(f[x]); return f[x]; } void unite(int x,int y) { int a=find(x),b=find(y); if(a!=b)f[b]=a; } void solve() { while(cin>>n>>m) { for(int i=0;i<N;i++)f[i]=i; for(int i=1;i<=m;i++) { int x,y; cin>>x>>y; unite(x,y); } int res=0; for(int i=1;i<=n;i++) if(f[i]==i)res++; cout<<res-1<<endl; } } signed main() { io; // cin>>_; // while(_--) solve(); return 0; }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
D - 朋友
#include <bits/stdc++.h> using namespace std; const double pi = acos(-1.0); #define x first #define y second #define LL long long #define int LL #define pb push_back #define all(v) (v).begin(),(v).end() #define PII pair<int,int> #define ll_INF 0x7f7f7f7f7f7f7f7f #define INF 0x3f3f3f3f #define debug(x) cerr << #x << ": " << x << endl #define io ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr) LL Mod(LL a,LL mod){return (a%mod+mod)%mod;} LL lowbit(LL x){return x&-x;}//最低位1及其后面的0构成的数值 LL qmi(LL a,LL b,LL mod) {LL ans = 1; while(b){ if(b & 1) ans = ans * (a % mod) % mod; a = a % mod * (a % mod) % mod; b >>= 1;} return ans; } int _; int n,m,p,q; const int N=500010; int f[N]; int find(int x) { if(x!=f[x])f[x]=find(f[x]); return f[x]; } void unite(int x,int y) { int a=find(x),b=find(y); if(a!=b) f[b]=a; } void solve() { cin>>n>>m>>p>>q; for(int i=1;i<N;i++)f[i]=i; for(int i=1;i<=p;i++) { int x,y; cin>>x>>y; unite(x,y); } for(int i=1;i<=q;i++) { int x,y; cin>>x>>y; x=-x+n; y=-y+n; unite(x,y); } int res1=0,res2=0; for(int i=1;i<=n;i++)if(find(i)==find(1))res1++; for(int i=n+1;i<=n+m;i++)if(find(i)==find(n+1))res2++; cout<<min(res1,res2)<<endl; } signed main() { io; // cin>>_; // while(_--) solve(); return 0; }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
E - Cthulhu
#include <bits/stdc++.h> using namespace std; const double pi = acos(-1.0); #define x first #define y second #define LL long long #define int LL #define pb push_back #define all(v) (v).begin(),(v).end() #define PII pair<int,int> #define ll_INF 0x7f7f7f7f7f7f7f7f #define INF 0x3f3f3f3f #define debug(x) cerr << #x << ": " << x << endl #define io ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr) LL Mod(LL a,LL mod){return (a%mod+mod)%mod;} LL lowbit(LL x){return x&-x;}//最低位1及其后面的0构成的数值 LL qmi(LL a,LL b,LL mod) {LL ans = 1; while(b){ if(b & 1) ans = ans * (a % mod) % mod; a = a % mod * (a % mod) % mod; b >>= 1;} return ans; } int _; int n,m; const int N=110,M=N*N; int f[N]; struct node { int a,b; }e[M]; int find(int x) { if(x!=f[x])f[x]=find(f[x]); return f[x]; } void unite(int x,int y) { int a=find(x),b=find(y); if(a!=b)f[b]=a; } void solve() { cin>>n>>m; if(n!=m) { cout<<"NO"<<endl; return; } for(int i=1;i<=n;i++)f[i]=i; for(int i=0;i<m;i++) { int a,b; cin>>a>>b; e[i]={a,b}; } int res=0; for(int i=0;i<m;i++) { int a=find(e[i].a),b=find(e[i].b); if(a!=b)unite(a,b); else { res++; } } if(res==1)cout<<"FHTAGN!"<<endl; else cout<<"NO"<<endl; } signed main() { io; // cin>>_; // while(_--) solve(); return 0; }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
F - DZY Loves Chemistry
#include <bits/stdc++.h> using namespace std; #define int long long #define pb push_back #define all(v) (v).begin(),(v).end() #define PII pair<int,int> #define io ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr) int n,m; const int N=10010; bool st[N]; vector<int>v[N]; int res=1; int dfs(int u) { st[u]=true; for(int i=0;i<v[u].size();i++) { if(!st[v[u][i]]) { res*=2; dfs(v[u][i]); } } return res; } signed main() { io; cin>>n>>m; while(m--) { int a,b; cin>>a>>b; v[a].pb(b); v[b].pb(a); } int maxv=0; for(int i=1;i<=n;i++) { if(!st[i])maxv=max(maxv,dfs(i)); } cout<<maxv<<endl; return 0; }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
G - Mocha and Diana (Easy Version)
#include <bits/stdc++.h> using namespace std; const double pi = acos(-1.0); #define x first #define y second #define LL long long #define int LL #define pb push_back #define all(v) (v).begin(),(v).end() #define PII pair<int,int> #define ll_INF 0x7f7f7f7f7f7f7f7f #define INF 0x3f3f3f3f #define debug(x) cerr << #x << ": " << x << endl #define io ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr) LL Mod(LL a,LL mod){return (a%mod+mod)%mod;} LL lowbit(LL x){return x&-x;}//最低位1及其后面的0构成的数值 LL qmi(LL a,LL b,LL mod) {LL ans = 1; while(b){ if(b & 1) ans = ans * (a % mod) % mod; a = a % mod * (a % mod) % mod; b >>= 1;} return ans; } int _; int n,m1,m2; const int N=2e5+10; int f1[N],f2[N]; int find1(int x) { if(x!=f1[x])f1[x]=find1(f1[x]); return f1[x]; } int find2(int x) { if(x!=f2[x])f2[x]=find2(f2[x]); return f2[x]; } void unite1(int x,int y) { int a=find1(x),b=find1(y); if(a!=b)f1[b]=a; } void unite2(int x,int y) { int a=find2(x),b=find2(y); if(a!=b)f2[b]=a; } void solve() { cin>>n>>m1>>m2; for(int i=0;i<N;i++)f1[i]=f2[i]=i; for(int i=1;i<=m1;i++) { int a,b; cin>>a>>b; unite1(a,b); } for(int i=1;i<=m2;i++) { int a,b; cin>>a>>b; unite2(a,b); } vector<PII>v; for(int i=1;i<=n;i++) { for(int j=i+1;j<=n;j++) { int a1=find1(i),b1=find1(j),a2=find2(i),b2=find2(j); if(a1!=b1&&a2!=b2) { v.pb({i,j}); unite1(a1,b1); unite2(a2,b2); } } } cout<<v.size()<<endl; for(auto x:v)cout<<x.x<<' '<<x.y<<endl; } signed main() { io; // cin>>_; // while(_--) solve(); return 0; }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
- 72
- 73
- 74
- 75
- 76
- 77
- 78
- 79
- 80
- 81
- 82
H - Cow and Snacks
#include <bits/stdc++.h> using namespace std; const double pi = acos(-1.0); #define x first #define y second #define LL long long #define int LL #define pb push_back #define all(v) (v).begin(),(v).end() #define PII pair<int,int> #define ll_INF 0x7f7f7f7f7f7f7f7f #define INF 0x3f3f3f3f #define debug(x) cerr << #x << ": " << x << endl #define io ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr) LL Mod(LL a,LL mod){return (a%mod+mod)%mod;} LL lowbit(LL x){return x&-x;}//最低位1及其后面的0构成的数值 LL qmi(LL a,LL b,LL mod) {LL ans = 1; while(b){ if(b & 1) ans = ans * (a % mod) % mod; a = a % mod * (a % mod) % mod; b >>= 1;} return ans; } int _; int n,m; const int N=1e5+10; int f[N]; struct node { int a,b; }e[N]; int find(int x) { if(x!=f[x])f[x]=find(f[x]); return f[x]; } void unite(int x,int y) { int a=find(x),b=find(y); if(a!=b)f[b]=a; } void solve() { cin>>n>>m; for(int i=1;i<=n;i++)f[i]=i; for(int i=0;i<m;i++) { int a,b; cin>>a>>b; e[i]={a,b}; } int res=0; for(int i=0;i<m;i++) { int a=find(e[i].a),b=find(e[i].b); if(a!=b)unite(a,b),res++; } cout<<m-res<<endl; } signed main() { io; // cin>>_; // while(_--) solve(); return 0; }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
I - Social Network
#include <bits/stdc++.h> using namespace std; const double pi = acos(-1.0); #define x first #define y second #define LL long long #define int LL #define pb push_back #define all(v) (v).begin(),(v).end() #define PII pair<int,int> #define ll_INF 0x7f7f7f7f7f7f7f7f #define INF 0x3f3f3f3f #define debug(x) cerr << #x << ": " << x << endl #define io ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr) LL Mod(LL a,LL mod){return (a%mod+mod)%mod;} LL lowbit(LL x){return x&-x;}//最低位1及其后面的0构成的数值 LL qmi(LL a,LL b,LL mod) {LL ans = 1; while(b){ if(b & 1) ans = ans * (a % mod) % mod; a = a % mod * (a % mod) % mod; b >>= 1;} return ans; } int _; int n,m; const int N=1e3+10; int f[N],cnt[N]; int res; int find(int x) { if(x!=f[x])f[x]=find(f[x]); return f[x]; } void unite(int x,int y) { int a=find(x),b=find(y); if(a!=b) { cnt[a]+=cnt[b]; f[b]=a; } else res++; } void solve() { cin>>n>>m; for(int i=1;i<=n;i++)f[i]=i,cnt[i]=1; for(int i=1;i<=m;i++) { int a,b; cin>>a>>b; unite(a,b); vector<int>v; for(int j=1;j<=n;j++) { if(f[j]==j)v.pb(cnt[j]); } sort(all(v),greater<int>()); int ans=0; for(int j=0;j<v.size()&&j<=res;j++) ans+=v[j]; ans--; cout<<ans<<endl; } } signed main() { io; // cin>>_; // while(_--) solve(); return 0; }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
J. pSort
#include <bits/stdc++.h> using namespace std; const double pi = acos(-1.0); #define x first #define y second #define LL long long #define int LL #define pb push_back #define all(v) (v).begin(),(v).end() #define PII pair<int,int> #define ll_INF 0x7f7f7f7f7f7f7f7f #define INF 0x3f3f3f3f #define debug(x) cerr << #x << ": " << x << endl #define io ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr) LL Mod(LL a,LL mod){return (a%mod+mod)%mod;} LL lowbit(LL x){return x&-x;}//最低位1及其后面的0构成的数值 LL qmi(LL a,LL b,LL mod) {LL ans = 1; while(b){ if(b & 1) ans = ans * (a % mod) % mod; a = a % mod * (a % mod) % mod; b >>= 1;} return ans; } int _; int n,m; const int N=110; int f[N]; int a[N],b[N]; int find(int x) { if(x!=f[x])f[x]=find(f[x]); return f[x]; } void unite(int x,int y) { int a=find(x),b=find(y); if(a!=b)f[b]=a; } bool check(int x,int y) { int a=find(x),b=find(y); return a==b; } void solve() { cin>>n; for(int i=1;i<=n;i++)f[i]=i; for(int i=1;i<=n;i++)cin>>a[i]; for(int i=1;i<=n;i++)cin>>b[i]; for(int i=1;i<=n;i++) { if(i-b[i]>=1)unite(i-b[i],i); if(i+b[i]<=n)unite(i+b[i],i); } for(int i=1;i<=n;i++) { if(!check(i,a[i])) { cout<<"NO"<<endl; return; } } cout<<"YES"<<endl; } signed main() { io; // cin>>_; // while(_--) solve(); return 0; }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
-
相关阅读:
DNS解析流程
C++设计模式（Design Patterns）
Leetcode13. 罗马数字转整数
平台项目列表页实现（二）
Java黑马程序员day11--集合进阶（上部--单列集合）
Docker从入门到部署项目
【从零学习python 】62. Python正则表达式：强大的字符串匹配工具
基于jsp+mysql+Spring+mybatis的SSM旅游服务综合平台管理系统
制作一个简单HTML宠物猫网页（HTML+CSS）
Java应用工程结构
- 原文地址：https://blog.csdn.net/qq_52765554/article/details/125532437
