Powered by:AB_IN 局外人
find和join函数
inline void finit () { for(int i=1;i<=n;i++) fa[i]=i; } inline int find(int x) { if(fa[x] == x) return x; return fa[x] = find(fa[x]); } inline void join(int a,int b) { int a1=find(a),b1=find(b); if(a1!=b1) fa[a1]=b1; }这个题就是给了你一些现有的路线，问还需要多少将它们都连起来？ 其实就是问父节点之间的连线。 父 节 点 的 个 数 − 1 父节点的个数-1 父节点的个数−1即可。
#include <bits/stdc++.h> using namespace std; int n, m, ans, a, b, u, v; int fa[1005]; #define rep(i,x,y) for (int i=(x);i<=(y);i++) int find(int x) { if(fa[x] == x) return x; return fa[x] = find(fa[x]); } void join(int a,int b) { int a1=find(a),b1=find(b); if(a1!=b1) fa[a1]=b1; } int main() { while(cin>>n>>m){ ans=0; rep(i,1,n) fa[i] = i; rep(i,1,m) { cin>>a>>b; join(a,b); } rep(i,1,n) if(find(i)==i) ans++; cout<<ans-1<<endl; } return 0; }相当于把下标变成字符串，一样做。
#include <bits/stdc++.h> #define rep(i,x,y) for (int i=(x);i<=(y);i++) using namespace std; map<string,string>fa; string find(string x) { if(fa[x] == x) return x; return fa[x] = find(fa[x]); } string name,name1,name2,u,v;; int n,m,t; int main() { cin>>n>>m; rep(i,1,n){ cin>>name; fa[name]=name; } rep(i,1,m){ cin>>name1>>name2; u=find(name1);v=find(name2); fa[u]=v; } cin>>t; while(t--){ cin>>name1>>name2; u=find(name1);v=find(name2); if(u==v) cout<<"Yes."<<endl; else cout<<"No."<<endl; } return 0; }定义两个数组，一个是结构体数组，用来存储数据。一个是fa数组，用来进行并查集操作。当村庄减到只剩1时，输出时间即可。
#include <bits/stdc++.h> typedef long long ll; #define rep(i,x,y) for (ll i=(x);i<=(y);i++) using namespace std; struct sa{ ll x,y,t; }a[200005]; int fa[200005]; ll find(ll x) { if(fa[x] == x) return x; return fa[x] = find(fa[x]); } ll cmp(struct sa &a,struct sa &b){ if(a.t!=b.t) return a.t<b.t; } ll n,m,u,v; namespace IO{ char ibuf[1<<21],*ip=ibuf,*ip_=ibuf; char obuf[1<<21],*op=obuf,*op_=obuf+(1<<21); inline char gc(){ if(ip!=ip_)return *ip++; ip=ibuf;ip_=ip+fread(ibuf,1,1<<21,stdin); return ip==ip_?EOF:*ip++; } inline void pc(char c){ if(op==op_)fwrite(obuf,1,1<<21,stdout),op=obuf; *op++=c; } inline ll read(){ register ll x=0,ch=gc(),w=1; for(;ch<'0'||ch>'9';ch=gc())if(ch=='-')w=-1; for(;ch>='0'&&ch<='9';ch=gc())x=x*10+ch-48; return w*x; } template<class I> inline void write(I x){ if(x<0)pc('-'),x=-x; if(x>9)write(x/10);pc(x%10+'0'); } class flusher_{ public: ~flusher_(){if(op!=obuf)fwrite(obuf,1,op-obuf,stdout);} }IO_flusher; } using namespace IO; int main() { n=read();m=read(); rep(i,1,m) a[i].x=read(),a[i].y=read(),a[i].t=read(); rep(i,1,n) fa[i]=i; sort(a+1,a+1+m,cmp); rep(i,1,m){ u=find(a[i].x); v=find(a[i].y); if(u!=v) fa[u]=v,n--; if(n==1) {write(a[i].t);return 0;} } write(-1); return 0; }大佬的题解
#include <bits/stdc++.h> const int maxn=5e4+5; int fa[3*maxn]; using namespace std; int find(int x) { if(fa[x] == x) return x; return fa[x] = find(fa[x]); } void join(int a,int b) { int a1=find(a),b1=find(b); if(a1!=b1) fa[a1]=b1; } int n,k,ans,op1,u,v; int main() { cin>>n>>k; for(int i=1;i<=3*n;i++) fa[i]=i; while(k--){ cin>>op1>>u>>v; if(u>n||v>n) ans++; else if(op1==1){ if(find(u+n)==find(v)||find(u)==find(v+n)) ans++;//判断是否u吃v，或者v吃u。 else{ join(u,v); join(u+n,v+n); join(u+n+n,v+n+n); } } else{ if(find(u)==find(v)/*包含了u吃u*/||find(v)==find(u+n)/*判断是否v吃u*/) ans++; else{ join(u,v+n); join(u+n,v+n+n); join(u+n+n,v); } } } cout<<ans<<endl; return 0; }完结。
