点双连通分量
-
定义：若在无向图 \(G\) 中，存在一个极大子图 \(G'\)，使得 \(G'\) 中没有割点，则称 \(G'\) 为 \(G\) 的一个点双连通分量，记作 \(\texttt{V-DCC}\)。
-
性质：一个点可能在多个 \(\texttt{V-DCC}\) 中，且这些点一定为割点。
-
求取：我们使用类似强连通分量求取的方法，使用一个栈存储访问过的节点，每当找到一个「可能的割点」（即不一定两边都有联通块），就将它以及后边的节点记入同一个 \(\texttt{V-DCC}\)，注意一下割点不能从栈中删除即可。
P8435
模板。
code
#include<bits/stdc++.h>
using namespace std;
const int N=2e6+5;
int n,m,rt,cnt,id;
int dfn[N],low[N];
vector<int> G[N],dcc[N];
stack<int> stk;
void tarjan(int cur){
dfn[cur]=low[cur]=++cnt;
stk.push(cur);
if(cur==rt&&!G[cur].size()){
dcc[++id].push_back(cur);
return;
}
for(int i:G[cur]){
if(!dfn[i]){
tarjan(i);
low[cur]=min(low[cur],low[i]);
if(low[i]>=dfn[cur]){
int now=0; ++id;
while(!stk.empty()&&now!=i){
now=stk.top();
dcc[id].push_back(now);
stk.pop();
}
dcc[id].push_back(cur);
}
}
else
low[cur]=min(low[cur],dfn[i]);
}
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cin>>n>>m;
for(int i=1,u,v;i<=m;i++){
cin>>u>>v;
if(u==v)
continue;
G[u].push_back(v);
G[v].push_back(u);
}
for(int i=1;i<=n;i++)
if(!dfn[i])
rt=i,tarjan(i);
cout<<id<<'\n';
for(int i=1;i<=id;i++){
cout<<dcc[i].size()<<' ';
for(int j:dcc[i])
cout<<j<<' ';
cout<<'\n';
}
return 0;
}
CF51F
诈骗题。
首先看到毛毛虫是一个树形结构，不难想到边双缩成一棵树（其实严格来说是一棵树加很多个自环，但是毛毛虫允许自环所以这不重要）。
考虑到毛毛虫需要一条主链，从贪心的角度考虑，选直径是最优的。
那么其他的点就必须操作吗？画图可以发现，叶子节点无需操作，因为它们可以在其他点合并的过程中带到主链的旁边去。注意这里的「叶子节点」是除去直径两端的叶子节点。
然后这题就没了。时间复杂度是 \(O(n+m)\) 的。
确实不难，个人认为最重要的是从毛毛虫本身的特点出发思考说需要用的算法，也即挖掘性质。
code
//
// 绝世好（唐）题.cpp
//
//
// Created by _XOFqwq on 2024/11/23.
//
#include <bits/stdc++.h>
using namespace std;
const int N=2e3+5,M=1e5+5;
int n,m;
int p,cnt,tot,id,dia;
int sumsiz,one,sumv;
int dfn[N],low[N];
int dcc[N],blk[N],siz[N],d[N];
bool ok[N][N];
bool bridge[M];
struct EDGE{
int v,i;
};
vector<EDGE> G[N];
vector<int> V[N];
void tarjan(int cur,int edg){
dfn[cur]=low[cur]=++cnt;
for(auto nxt:G[cur]){
if(!dfn[nxt.v]){
tarjan(nxt.v,nxt.i);
low[cur]=min(low[cur],low[nxt.v]);
if(low[nxt.v]>dfn[cur])
bridge[nxt.i]=1;
}
else if(nxt.i!=edg)
low[cur]=min(low[cur],dfn[nxt.v]);
}
}
void getdcc(int cur){
dcc[cur]=id;
siz[id]++;
for(auto nxt:G[cur]){
if(bridge[nxt.i]||dcc[nxt.v])
continue;
getdcc(nxt.v);
}
}
void dfs(int cur){
blk[cur]=tot;
sumsiz+=siz[cur]-1;
one+=(d[cur]==1);
sumv++;
for (int i:V[cur]) {
if (!blk[i]) {
dfs(i);
}
}
}
void getdia(int cur,int fa,int sum){
if(sum>=dia){
dia=sum;
p=cur;
}
for(int i:V[cur]){
if(i==fa)
continue;
getdia(i,cur,sum+1);
}
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cin>>n>>m;
for (int i=1,u,v; i<=m; i++) {
cin>>u>>v;
G[u].push_back({v,i});
G[v].push_back({u,i});
}
for (int i=1; i<=n; i++) {
if (!dfn[i]) {
tarjan(i,0);
}
}
for (int i=1; i<=n; i++) {
if (!dcc[i]) {
++id,getdcc(i);
}
}
for (int i=1; i<=n; i++) {
for (auto nxt : G[i]) {
if (dcc[i]!=dcc[nxt.v]&&!ok[dcc[i]][dcc[nxt.v]]) {
V[dcc[i]].push_back(dcc[nxt.v]);
V[dcc[nxt.v]].push_back(dcc[i]);
d[dcc[i]]++;
d[dcc[nxt.v]]++;
ok[dcc[i]][dcc[nxt.v]]=ok[dcc[nxt.v]][dcc[i]]=1;
}
}
}
int ans=0;
for (int i=1; i<=id; i++) {
if (!blk[i]) {
++tot;
sumsiz=one=p=sumv=0;
dia=-1e9;
dfs(i);
getdia(i,0,1);
getdia(p,0,1);
ans+=sumsiz+sumv-(dia+one-(!one?0:2));
}
}
ans+=tot-1;
cout<<ans;
return 0;
}
CF962F
tj。
标签：Living,cur,nxt,int,id,dfn,low,Dream,87 From： https://www.cnblogs.com/XOF-0-0/p/18591153