P10179题解
wangif424
·
·
题解
部分分
Subtask5
对于所有的 $v_i$，满足 $dis(1,v_i)=2$，那么考虑找一个点 $x$ 为中心建菊花图，如果存在可行的点 $x$，则有解，否则无解。
### Subtask6
$u_i \neq 1,v_i \neq 1$。
以 $1$ 为中心建菊花图即可。
~~剩下的部分分不会打~~。
# 正解
对每一组限制连边，跑`dfs`得出每个点所属于的连通块以及每个连通块大小。
因为每组限制 $(u_i,v_i)$ 满足在树上距离为 $2$，那么在我们建的图中属于一个连通块的点在树上的距离一定为偶数。
有上述结论可以得到 $(x,y),(y,z) \Leftrightarrow (x,y),(x,z)$。
于是所有的点被分成了两类：能和 $1$ 直接相连的以及不能的。
如果所有的点都不能与 $1$ 直接相连，那么此时无解。
对于能和 $1$ 直接相连的，则直接连 $1$。
对于不能的，在上面能和 $1$ 直接相连的点中任取一个相连就好。
# AC代码
```cpp
#include<bits/stdc++.h>
#define R(x) x=read()
using namespace std;
char pbuf[1<<20], *pp=pbuf;
void swap(int a,int b){a^=b^=a^=b;}
inline void push(const char &c){if(pp - pbuf == 1<<20)fwrite(pbuf, 1, 1<<20, stdout),pp = pbuf;*pp++ = c;}
class io{public:~io(){fwrite(pbuf, 1, pp - pbuf, stdout);}}_;
inline void write(int x) {
if (x<0)x=-x,push('-');
int sta[35],top=0;
do{sta[top++]=x%10,x/=10;}while (x);
while(top)push(sta[--top]^'0');
}
#ifndef LOCAL
char buf[1<<23],*p1=buf,*p2=buf,obuf[1<<23],*O=obuf;
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
#endif
inline int read() {
int x=0,f=1;char ch=getchar();
while(!isdigit(ch)){if(ch=='-') f=-1;ch=getchar();}
while(isdigit(ch)) x=x*10+(ch^48),ch=getchar();
return x*f;
}
int t;
int n,m;
struct edge{
int to,nxt;
}v[600100];
int len,fir[300100];
void add(int x,int y){
++len;
v[len].to=y;
v[len].nxt=fir[x];
fir[x]=len;
}
int vis[300100];
int cnt[300100];
void clear(){
len=0;
memset(fir,0,sizeof(fir));
memset(vis,0,sizeof(vis));
memset(cnt,0,sizeof(cnt));
}
int x[300100],y[300100];
void dfs(int u,int fa,int c){
if(vis[u])return;
vis[u]=c;
cnt[c]++;
for(int i=fir[u];i;i=v[i].nxt){
if(v[i].to==fa)continue;
dfs(v[i].to,u,c);
}
}
bool check(){
for(int i=1;i<=n;i++){
if(cnt[i]==n){
push('N');
push('o');
push('\n');
return 0;
}
}
return 1;
}
signed main(){
R(t);
while(t--){
clear();
R(n);R(m);
for(int i=1;i<=m;i++){
R(x[i]);
R(y[i]);
add(x[i],y[i]);
add(y[i],x[i]);
}
for(int i=1;i<=n;i++)if(!vis[i])dfs(i,0,i);
if(check()){
push('Y');push('e');push('s');push('\n');
int pos=1;
for(;pos<=n;pos++){
if(vis[pos]!=1)break;
}
for(int i=1;i<=n;i++){
if(vis[i]!=1){
write(1);push(' ');
write(i);push(' ');
push('\n');
}
}
for(int i=2;i<=n;i++){
if(vis[i]==1){
write(pos);push(' ');
write(i);push(' ');
push('\n');
}
}
}
}
return 0;
}
```