题解：P2247 SAC#1 - ACOJ云评测计划
DongbeiYJ
·
·
题解
很简单的一道题
题意
在一个 n 个点的图中找出 k 个点，使得删去这 k 个点后图不连通。
思路
我们注意到数据范围范围 k \le 3 和 n \le 500 数据很小，直接暴力就能过。
具体地：
$ k=2 $ 时，枚举删去 $ 1 $ 个点，在删去这个点后的图上求出割点，这 $ 2 $ 个点就是原图的割点集。
$ k=3 $ 时，同理枚举删去 $ 2 $ 个点后再求割点，这 $ 3 $ 个点就是原图的割点集。
**注意**：题目给的可能不是连通图，需要特判！
::::success[AC Code]
```cpp
#include <bits/stdc++.h>
using namespace std;
#define ll int
#define N 505
ll n,m,k;
struct node{
ll nx,to;
};
vector<node>e;
ll h[N*2];
void add(ll a,ll b){
e.push_back({h[a],b});
h[a]=e.size()-1;
e.push_back({h[b],a});
h[b]=e.size()-1;
}
ll root=1,tot,low[N],dfn[N],num;
bool cut[N],vis[N];
void tar(ll u,ll fa){
ll cnt=0;
low[u]=dfn[u]=++tot;
for(ll i=h[u];~i;i=e[i].nx){
ll v=e[i].to;
if(vis[v]) continue;
if(!dfn[v]){
cnt++;
tar(v,u);
low[u]=min(low[u],low[v]);
if((u==root&&cnt>=2)||(u!=root&&low[v]>=dfn[u])){
num++;
cut[u]=1;
}
}
else if(v!=fa) low[u]=min(low[u],dfn[v]);
}
}
void clear(){
root=1;
tot=0;
memset(dfn,0,sizeof dfn);
memset(low,0,sizeof low);
memset(cut,0,sizeof cut);
}
ll Root(ll a,ll b){
if(a==1||b==1){
for(ll i=2;i<=n;i++)
if(i!=a&&i!=b) return i;
}
else return 1;
}
int main(){
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
memset(h,-1,sizeof h);
cin>>n>>m>>k;
for(ll i=1;i<=m;i++){
ll u,v;
cin>>u>>v;
add(u,v);
}
tar(1,-1);
for(ll i=1;i<=n;i++){
if(!dfn[i]){
cout<<"Poor SOL!";
return 0;
}
}
if(k==1){
for(ll i=1;i<=n;i++)
if(cut[i]){
cout<<i;
return 0;
}
cout<<"How oversuspicious you are, SOL!";
}
if(k==2){
for(ll x=1;x<=n;x++){
clear();
vis[x]=1;
if(x==1){
root=2;
tar(2,-1);
}
else tar(1,-1);
vis[x]=0;
for(ll y=1;y<=n;y++){
if(y==x) continue;
if(cut[y]){
cout<<x<<' '<<y;
return 0;
}
}
}
cout<<"How oversuspicious you are, SOL!";
}
if(k==3){
for(ll x=1;x<=n;x++){
for(ll y=1;y<=n;y++){
if(x==y) continue;
clear();
root=Root(x,y);
vis[x]=vis[y]=1;
tar(root,-1);
vis[x]=vis[y]=0;
for(ll z=1;z<=n;z++){
if(z==x||z==y) continue;
if(cut[z]){
cout<<x<<' '<<y<<' '<<z;
return 0;
}
}
}
}
cout<<"How oversuspicious you are, SOL!";
}
return 0;
}
```
::::