正题
题目链接:https://ac.nowcoder.com/acm/contest/1101#question
题目大意
n
n
n个点
m
m
m条边的沙漠(所有联通子图都是仙人掌)，删除
k
k
k个点使得剩下的连通块最多。
解题思路
对于图上的每条割边，删去之后就可以多出一个联通块，所以我们就可以先删去所有割边。
之后图上剩下许多个环，没两个环之间由一个割点连接，所以我们可以用缩点双联通分量的方法找出所有的环。
我们发现对于每个环删除一条边之后就可以变成一条链，也就是我们删除
k
k
k条边就会多出
k
−
1
k-1
k−1个联通块。然后我们可以对于所有的环按照大小排序，然后从大的到小的分成链。
c
o
d
e
code
code
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<stack>
using namespace std
;
const int N
=1e6+10;
struct node
{
int to
,next
;
}a
[N
*4];
int n
,m
,k
,tot
=1,ans
,c
,cnt
,num
;
int dfn
[N
],low
[N
],ls
[N
],cir
[N
];
bool mark
[N
*4],flag
;
stack
<int> s
;
void addl(int x
,int y
)
{
a
[++tot
].to
=y
;
a
[tot
].next
=ls
[x
];
ls
[x
]=tot
;
}
void tarjan(int x
,int edge
)
{
dfn
[x
]=low
[x
]=++cnt
;
for(int i
=ls
[x
];i
;i
=a
[i
].next
)
{
int y
=a
[i
].to
;
if(!dfn
[y
]){
tarjan(y
,i
);
low
[x
]=min(low
[x
],low
[y
]);
if(low
[y
]>dfn
[x
]){
mark
[i
]=mark
[i
^1]=1;
if(k
) ans
++,k
--;
}
}
else if(i
!=(edge
^1))
low
[x
]=min(low
[x
],dfn
[y
]);
}
}
void tarjan2(int x
)
{
dfn
[x
]=low
[x
]=++cnt
;
s
.push(x
);
for(int i
=ls
[x
];i
;i
=a
[i
].next
)
{
if(mark
[i
]) continue;
int y
=a
[i
].to
;
if(!dfn
[y
]){
tarjan2(y
);num
=0;
low
[x
]=min(low
[x
],low
[y
]);
if(low
[y
]>=dfn
[x
]){
int z
;
do{
z
=s
.top();
num
++;s
.pop();
}while(z
!=y
);
num
++;cir
[++c
]=num
;
}
}
else low
[x
]=min(low
[x
],dfn
[y
]);
}
}
int main()
{
scanf("%d%d%d",&n
,&m
,&k
);
for(int i
=1;i
<=m
;i
++){
int x
,y
;
scanf("%d%d",&x
,&y
);
addl(x
,y
);addl(y
,x
);
}
for(int i
=1;i
<=n
;i
++)
if(!dfn
[i
])
tarjan(i
,0),ans
++;
cnt
=0;
memset(dfn
,0,sizeof(dfn
));
memset(low
,0,sizeof(low
));
for(int i
=1;i
<=n
;i
++)
if(!dfn
[i
])
tarjan2(i
);
sort(cir
+1,cir
+1+c
);
for(int i
=c
;i
>=1;i
--){
if(k
<2) break;
ans
+=min(k
,cir
[i
])-1;
k
-=min(k
,cir
[i
]);
}
printf("%d",ans
);
}
