E. Johnny Solving
题意：
输入
n
,
m
,
k
(
1
≤
k
≤
n
≤
2.5
×
1
0
5
,
1
≤
m
≤
5
×
1
0
5
)
n,m,k(1\leq k\leq n\leq 2.5\times10^5,1\leq m\leq 5\times10^5)
n,m,k(1≤k≤n≤2.5×105,1≤m≤5×105) 接下来
m
m
m行，每行
u
,
v
u,v
u,v,表示无向边。 表示一个有
m
m
m个点联通图，
m
m
m条边，并且保证每个点的度数至少为3；问(选择一种回答)：
若有大于等于
n
/
k
n/k
n/k长度的路径则输出若有
k
k
k个长度大于3且不被3整除的环，输出。
题解：
首先以1为根节点，构造一颗生成树。
若最远叶子节点到根节点的距离大于等于
n
/
k
n/k
n/k，直接输出即可。否则也就是所有叶子节点到根节点的距离都小于
n
/
k
n/k
n/k,所以叶子节点的个数必大于等于
k
k
k，因为每个节点的度至少为3，所以叶子节点
v
v
v必定至少和它的祖先
x
,
y
x,y
x,y相连，形成至少三个环，
d
e
p
[
v
]
−
d
e
p
[
x
]
+
1
,
d
e
p
[
v
]
−
d
e
p
[
y
]
+
1
,
d
e
p
[
x
]
−
d
e
p
[
y
]
+
2
dep[v]-dep[x]+1,dep[v]-dep[y]+1,dep[x]-dep[y]+2
dep[v]−dep[x]+1,dep[v]−dep[y]+1,dep[x]−dep[y]+2,三个中至少有一个不是3的倍数。 注意： 双向边，边数组范围要乘2，此题数据范围比较大，要加读入优化。
代码：
#include<bits/stdc++.h>
using namespace std
;
const int N
=5e5+9;
int n
,m
,k
;
struct Edge
{
int v
,nxt
;
}e
[N
<<1];
int head
[N
],cnt
;
inline void add(int u
,int v
){
e
[cnt
]=(Edge
){v
,head
[u
]};
head
[u
]=cnt
++;
}
int dep
[N
],f
[N
];
bool vis
[N
],leave
[N
];
int mx
;
void dfs(int u
){
if(dep
[u
]>dep
[mx
])mx
=u
;
vis
[u
]=leave
[u
]=1;
for(int i
=head
[u
],v
;~i
;i
=e
[i
].nxt
){
v
=e
[i
].v
;
if(vis
[v
])continue;
leave
[u
]=0;
dep
[v
]=dep
[u
]+1,f
[v
]=u
;
dfs(v
);
}
}
int main(){
ios
::sync_with_stdio(0),cin
.tie(0),cout
.tie(0);
cin
>>n
>>m
>>k
;
memset(head
,-1,sizeof(head
));
for(int i
=1,u
,v
;i
<=m
;i
++)cin
>>u
>>v
,add(u
,v
),add(v
,u
);
dep
[1]=1;
dfs(1);
if(dep
[mx
]>=n
/k
){
cout
<<"PATH\n";
cout
<<dep
[mx
]<<endl
;
while(mx
)cout
<<mx
<<" ",mx
=f
[mx
];cout
<<endl
;
return 0;
}else{
cout
<<"CYCLES\n";
for(int i
=1;i
<=n
&&k
;i
++)if(leave
[i
]){
k
--;
int x
=0,y
=0;
for(int j
=head
[i
];~j
;j
=e
[j
].nxt
){
if(e
[j
].v
==f
[i
])continue;
if(x
==0)x
=e
[j
].v
;
else {y
=e
[j
].v
;break;}
}
if((dep
[i
]-dep
[x
]+1)%3){
cout
<<dep
[i
]-dep
[x
]+1<<endl
;
int k
=i
;
while(1){cout
<<k
<<" ";if(k
==x
)break;k
=f
[k
];}
cout
<<endl
;
}else if((dep
[i
]-dep
[y
]+1)%3){
cout
<<dep
[i
]-dep
[y
]+1<<endl
;
int k
=i
;
while(1){cout
<<k
<<" ";if(k
==y
)break;k
=f
[k
];}
cout
<<endl
;
}else{
if(dep
[x
]>dep
[y
])swap(x
,y
);
cout
<<dep
[y
]-dep
[x
]+2<<endl
;
cout
<<i
<<" ";
int k
=y
;
while(1){cout
<<k
<<" ";if(k
==x
)break;k
=f
[k
];}
cout
<<endl
;
}
}
}
return 0;
}
