QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#777866 | #6421. Degree of Spanning Tree | WaterSun | WA | 37ms | 4044kb | C++14 | 2.5kb | 2024-11-24 10:30:32 | 2024-11-24 10:30:33 |
Judging History
answer
#include <bits/stdc++.h>
#define re register
#define fst first
#define snd second
using namespace std;
typedef pair<int,int> pii;
const int N = 2e5 + 10;
int n,m;
int f[N],deg[N];
bool vis[N];
inline int read(){
int r = 0,w = 1;
char c = getchar();
while (c < '0' || c > '9'){
if (c == '-') w = -1;
c = getchar();
}
while (c >= '0' && c <= '9'){
r = (r << 3) + (r << 1) + (c ^ 48);
c = getchar();
}
return r * w;
}
inline int find(int x){
if (f[x] != x) return f[x] = find(f[x]);
else return f[x];
}
inline void merge(int a,int b){
int x = find(a),y = find(b);
if (x == y) return;
if (vis[x]) swap(x,y);
f[x] = y;
}
int tot;
inline void solve(){
vector<pii> e1,e2;
n = read(),m = read();
if ((++tot) == 120) cout << n << " " << m << " nm\n";
fill(deg + 1,deg + n + 1,0);
fill(vis + 1,vis + n + 1,false);
for (re int i = 1;i <= n;i++) f[i] = i;
for (re int i = 1,a,b;i <= m;i++){
a = read(),b = read();
if (find(a) != find(b)){
merge(a,b);
deg[a]++; deg[b]++;
e1.push_back({a,b});
}
else e2.push_back({a,b});
}
if (tot > 2) return;
int rt = 0;
for (re int i = 1;i <= n;i++){
if (deg[i] > n / 2) rt = i;
}
if (!rt){
puts("Yes");
for (pii p:e1) printf("%d %d\n",p.fst,p.snd);
return;
}
for (re int i = 1;i <= n;i++) f[i] = i;
for (pii p:e1){
if (p.fst == rt) vis[p.snd] = true;
else if (p.snd == rt) vis[p.fst] = true;
}
for (pii p:e1){
if (p.fst != rt && p.snd != rt) merge(p.fst,p.snd);
}
for (pii p:e2){
if (p.fst != rt && p.snd != rt && find(p.fst) != find(p.snd)){
if (deg[p.fst] + 1 <= n / 2 && deg[p.snd] + 1 <= n / 2){
int x = find(p.fst),y = find(p.snd);
if (deg[x] < deg[y]) swap(x,y);
deg[x]--; deg[rt]--;
deg[p.fst]++; deg[p.snd]++;
vis[x] = false; merge(x,y);
e1.push_back(p);
}
}
}
if (deg[rt] > n / 2) puts("No");
else{
puts("Yes");
for (pii p:e1){
if (p.fst != rt && p.snd != rt) printf("%d %d\n",p.fst,p.snd);
}
for (re int i = 1;i <= n;i++){
if (vis[i]) printf("%d %d\n",rt,i);
}
}
}
int main(){
int T; T = read();
while (T--) solve();
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 3720kb
input:
2 6 9 1 2 1 3 1 4 2 3 2 4 3 4 4 5 4 6 4 6 3 4 1 3 2 3 3 3 1 2
output:
Yes 1 2 1 3 1 4 4 5 4 6 No
result:
ok 2 cases
Test #2:
score: -100
Wrong Answer
time: 37ms
memory: 4044kb
input:
11140 10 15 9 6 5 7 6 5 2 3 7 5 7 5 3 10 9 7 5 5 9 1 7 5 2 8 7 5 4 3 6 2 9 19 3 7 3 9 2 8 2 8 3 6 5 1 1 8 8 9 8 3 4 8 5 5 3 1 4 3 1 3 8 6 1 3 7 4 4 3 8 8 12 20 10 2 5 5 2 4 3 3 3 3 5 11 9 2 5 5 7 12 11 3 3 3 3 5 5 3 3 1 4 6 7 11 6 8 4 5 6 12 6 5 8 18 4 2 4 3 2 4 2 4 4 3 4 8 2 2 6 7 2 4 6 2 1 4 8 7 4...
output:
Yes 9 6 5 7 6 5 2 3 3 10 9 1 2 8 4 3 6 2 Yes 3 7 3 9 2 8 3 6 5 1 1 8 8 9 4 8 5 12 nm
result:
wrong answer Line "5 12 nm" doesn't correspond to pattern "Yes|No"