codeforces（D. Dogeforces） 并查集

原题链接


排序+并查集

代码：

//#pragma GCC optimize("Ofast")
//#pragma GCC target("avx,avx2,fma")
//#pragma GCC optimization ("unroll-loops")
#include 
#define pb push_back
#define ll long long
#define IOS std::ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;ll n,cnt;
ll a[505][505];
struct node
{ll val,x,y;
}e[1000006];
ll f[100005],k,root;
ll w[100005];
bool cmp(node a,node b)
{if(a.val<b.val){return 1;}if(a.val==b.val){if(a.x<b.x){return 1;}if(a.x==b.x){if(a.y<b.y){return 1;}return 0;}return 0;}return 0;
}
ll getf(ll u)
{if(f[u]==u){return f[u];}else{return getf(f[u]);}
}
void mange(ll u,ll v)
{ll t1=getf(u);ll t2=getf(v);if(t1!=t2){f[t2]=t1;}
}
void init()
{for(int i=0;i<=100000;i++){f[i]=i;}
}
int main()
{scanf("%lld",&n);for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){scanf("%lld",&a[i][j]);if(i==j){w[i]=a[i][j];}}}init();k=n;for(int i=1;i<=n;i++){for(int j=i+1;j<=n;j++){e[++cnt].val=a[i][j];e[cnt].x=i;e[cnt].y=j;}}sort(e+1,e+1+cnt,cmp);for(int i=1;i<=cnt;i++){if(i==1){f[e[i].x]=++k;f[e[i].y]=k;w[k]=e[i].val;continue;}ll f1=getf(e[i].x);ll f2=getf(e[i].y);if(w[f1]==e[i].val&&w[f2]==e[i].val){continue;}if(w[f1]==e[i].val){mange(f1,f2);continue;}if(w[f2]==e[i].val){mange(f2,f1);continue;}++k;w[k]=e[i].val;mange(k,f1);mange(k,f2);}ll base=0;for(int i=1;i<=k;i++){if(w[i]>base){base=w[i];root=i;}}cout<<k<<'\n';for(int i=1;i<=k;i++){cout<<w[i]<<" ";}cout<<'\n';cout<<root<<'\n';for(int i=1;i<=k;i++){if(i==root){continue;}cout<<i<<" "<<f[i]<<'\n';}return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！