QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#780525 | #6421. Degree of Spanning Tree | Symbolize | WA | 67ms | 26220kb | C++17 | 2.4kb | 2024-11-25 11:23:27 | 2024-11-25 11:23:28 |
Judging History
answer
/*
Luogu name: Symbolize
Luogu uid: 672793
*/
#include<bits/stdc++.h>
#define int long long
#define pii pair<int,int>
#define x first
#define y second
#define rep1(i,l,r) for(register int i=l;i<=r;++i)
#define rep2(i,l,r) for(register int i=l;i>=r;--i)
#define rep3(i,x,y,z) for(register int i=x[y];~i;i=z[i])
#define rep4(i,x) for(auto i:x)
#define debug() puts("----------")
const int N=5e5+10;
const int inf=0x3f3f3f3f3f3f3f3f;
using namespace std;
int t,n,m,fa[N],f[N],times[N],dep[N];
bool vis[N];
vector<pii> G[N];
struct Graph{int u,v;}e[N];
int read()
{
int x=0,f=1;
char ch=getchar();
while(ch<'0'||ch>'9')
{
if(ch=='-') f=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9')
{
x=(x<<1)+(x<<3)+(ch^48);
ch=getchar();
}
return f*x;
}
int find(int x)
{
if(x==fa[x]) return x;
return fa[x]=find(fa[x]);
}
void dfs(int x,int Fa,int top)
{
dep[x]=dep[Fa]+1;
fa[x]=top;
rep4(to,G[x])
{
if(to.x==Fa) continue;
dfs(to.x,x,top);
}
return;
}
void getans()
{
n=read();
m=read();
rep1(i,1,n)
{
G[i].clear();
fa[i]=i;
times[i]=0;
}
rep1(i,1,m) vis[i]=0;
rep1(i,1,m)
{
e[i].u=read();
e[i].v=read();
int x=find(e[i].u),y=find(e[i].v);
if(x==y) continue;
G[x].push_back(make_pair(y,i));
G[y].push_back(make_pair(x,i));
fa[x]=y;
vis[i]=1;
++times[e[i].u];
++times[e[i].v];
}
if(n==3)
{
puts("No");
return;
}
int rt=0;
rep1(i,1,n) if(times[i]>n/2) rt=i;
fa[rt]=rt;
rep4(to,G[rt])
{
f[to.x]=to.y;
dfs(to.x,rt,to.x);
}
rep1(i,1,m)
{
if(times[rt]<=n/2) break;
int x=find(e[i].u),y=find(e[i].v);
if(x==y||x==rt||y==rt) continue;
if(dep[e[i].u]>dep[e[i].v]) swap(e[i].u,e[i].v),swap(x,y);
if(dep[e[i].u]==1&×[e[i].u]<times[e[i].v]) swap(e[i].u,e[i].v),swap(x,y);
fa[x]=y;
vis[f[x]]=0;
vis[i]=1;
--times[x];
--times[rt];
++times[e[i].u];
++times[e[i].v];
}
if(times[rt]>n/2) puts("No");
else
{
// rep1(i,1,n)
// {
// if(times[i]>n/2)
// {
// debug();
// cout<<n<<' '<<m<<"\n";
// rep1(j,1,m) cout<<e[j].u<<' '<<e[j].v<<"\n";
// }
// }
puts("Yes");
rep1(i,1,m) if(vis[i]) cout<<e[i].u<<' '<<e[i].v<<"\n";
}
return;
}
signed main()
{
// freopen(".in","r",stdin);
// freopen(".out","w",stdout);
t=read();
while(t--) getans();
return 0;
}
/*
1
3 4
1 3
2 3
3 3
1 2
*/
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 22132kb
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: 67ms
memory: 26220kb
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 Yes 10 2 2 4 5 11 9 2 7 12 11 3 3 1 4 6 7 11 6 8 4 5 Yes 4 2 4 3 4 8 6 7 6 2 1 4 7 5 Yes 6 5 5 7 5 9 4 3 2 9 2 3 8 7 5 1 Yes 10 2 2 6 3 2 1 9 8 10 4 6 6 1 2 5 1 7 Yes 5 7 5 4 7 1 2 6 6 7 1 3 Yes 12 3 1 13 7 8 8 2 10 6 1 6 1...
result:
wrong output format Expected integer, but "Yes" found