QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#780352	#6421. Degree of Spanning Tree	ASnown	RE	1ms	5816kb	C++17	2.2kb	2024-11-25 10:20:48	2024-11-25 10:20:49

Judging History

你现在查看的是最新测评结果

[2024-11-25 10:20:49]
评测

测评结果：RE
用时：1ms
内存：5816kb

查看

[2024-11-25 10:20:48]
提交

answer

#include<bits/stdc++.h>
#define file(F) freopen(#F".in","r",stdin),freopen(#F".out","w",stdout)
#define lowbit(x) ((x)&-(x))
#define ALL(x) (x).begin(),(x).end()
#define debug(...) fprintf(stderr,__VA_ARGS__)
#define popc(x) (__builtin_popcountll((x)))
#define abs(x) ((x)>=0?(x):-(x))
using namespace std;
using ll=long long;
using uint=uint32_t;
template<typename T>
inline bool Max(T &x,T y) { return std::less<T>()(x,y)&&(x=y,true); }
template<typename T>
inline bool Min(T &x,T y) { return std::less<T>()(y,x)&&(x=y,true); }
void Solve();
const int N = 2e5+25;
int n,m;
int deg[N];
pair<int,int> G[N];
int p[N];
int Find(int x) { return x==p[x]?x:p[x]=Find(p[x]); }
void Union(int x,int y) { if((x=Find(x))!=(y!=Find(y))) p[y]=x; }
signed main() {
#ifndef ONLINE_JUDGE
#endif
   cin.tie(nullptr)->sync_with_stdio(false);
   int T; cin>>T; while(T--)
   Solve();
}
void Solve() {
   cin>>n>>m;
   iota(p+1,p+n+1,1),fill(deg+1,deg+n+1,0);
   vector<pair<int,int>> ans;
   for(int i=1;i<=m;i++) {
      int u,v; cin>>u>>v;
      if(u==v) { --i,--m; continue; }
      G[i]={u,v};
      if(Find(u)!=Find(v)) {
         ++deg[u],++deg[v];
         Union(u,v);
         ans.emplace_back(u,v);
      }
   }
   int rt=-1;
   for(int i=1;i<=n;i++) if(deg[i]>n/2) rt=i;
   if(!~rt) {
      puts("Yes");
      for(auto E:ans) printf("%d %d\n",E.first,E.second);
      return ;
   }
   iota(p+1,p+n+1,1);
   vector<int> son;
   vector<pair<int,int>> tans; tans.swap(ans);
   for(auto E:tans) {
      int u,v; tie(u,v)=E;
      if(u==rt||v==rt) {
         son.emplace_back(u==rt?v:u);
         continue;
      }
      if(Find(u)!=Find(v)) {
         Union(u,v);
         ans.emplace_back(u,v);
      }
   }
   for(int i=1;i<=m;i++) {
      int u,v; tie(u,v)=G[i];
      if(u==rt||v==rt||Find(u)==Find(v)) continue;
      Union(u,v);
      ++deg[u],++deg[v];
      ans.emplace_back(u,v);
      if(--deg[rt]<=n/2) break;
   }
   for(auto x:son) if(Find(x)!=Find(rt)&&deg[x]<=n/2)
      Union(x,rt),ans.emplace_back(x,rt);
   assert(ans.size()<=n-1);
   if(ans.size()!=n-1) return void(puts("No"));
   puts("Yes");
   for(auto E:ans) printf("%d %d\n",E.first,E.second);
}

源文件, 语言: C++17

详细

Test #1:

score: 100

Accepted

time: 1ms

memory: 5816kb

input:

output:

result:

ok 2 cases

Test #2:

score: -100

Runtime Error

input: