点双连通分量¶
点双连通分量指的是在一个无向图中，极大的一组顶点和边，使得任意两个顶点间都有至少两条不相交的路径（即即使删除图中的一个顶点，这些顶点仍然是连通的）。换句话说，点双连通分量中的任意两个顶点间都是点双连通的。
例题 #1¶
对于一个 \(n\) 个节点 \(m\) 条无向边的图，请输出其点双连通分量的个数，并且输出每个点双连通分量。
提示&代码
注意一个点可能属于多个vdcc，所以不可用belong[]存储，而应该直接推入(vector) vdcc[cnt]中
完整代码
/*////////ACACACACACACAC///////////
. Code by Ntsc .
. Earn knowledge .
/*////////ACACACACACACAC///////////
#include<bits/stdc++.h>
#define int long long
#define db double
#define rtn return
using namespace std;
const int N=5e5+5;
const int M=5e6;
const int Mod=1e5;
const int INF=1e5;
int n,m,p,T;
int dfn[N],low[N],indx;//时间戳，追溯值，给时间戳编号的计数器
int stk[N],tp;//栈，指针
bool instk[N]; //是否在栈中
int belong[N],siz[N],vdcc; //记录每个点在那个边双连通分量里, 每个点所在的边双连通分量的大小,边双连通分量的数量
vector<int> ans[N];
int vis[N];
struct edge{
int to,nxt;
}e[M];
int h[N],idx=-1;
void add(int a,int b){
e[++idx]={b,h[a]};
h[a]=idx;
e[++idx]={a,h[b]};
h[b]=idx;
}
void tarjan(int u,int fa) {//当前节点,入边的节点编号
int son=0;//判孤立点用
vis[u]=1;
dfn[u]=low[u]=++indx;
stk[++tp]=u;
for(int i=h[u]; ~i; i=e[i].nxt) {
int v=e[i].to;
if(dfn[v]==0) {
son++;
tarjan(v,u);//not tarjan(v,i);
low[u]=min(low[u],low[v]);
///new
if(low[v]>=dfn[u]){
vdcc++;
int x;
do {
x=stk[tp--];
ans[vdcc].push_back(x);//注意！一个点可能属于多个vdcc!
} while(x!=v);
ans[vdcc].push_back(u);
}
}
else if(v!=fa) low[u]=min(low[u],dfn[v]);//判断点是否相同，而边双中是判断边是否和来时的边的反向边相同，都是为了防止回头
}
if(!(fa||son))ans[++vdcc].push_back(u);//特判孤立点
}
signed main(){
int m,n;
cin>>n>>m;
for(int i=1;i<=N;i++)e[i].nxt=-1,h[i]=-1;
for(int i=1;i<=m;i++){
int a,b;
cin>>a>>b;
add(a,b);
}
for(int i=1;i<=n;i++)if(!vis[i])tp=0,tarjan(i,0);//图可能不连通！切勿重复访问！
cout<<vdcc<<endl;
for(int i=1;i<=vdcc;i++){
cout<<ans[i].size()<<' ';
for(auto v:ans[i])cout<<v<<' ';
cout<<endl;
}
return 0;
}
例题 #2 KNIGHTS - Knights of the Round Table¶
题目大意
有 \(n\) 个骑士经常举行圆桌会议，商讨大事。每次圆桌会议至少有 \(3\) 个骑士参加，且相互憎恨的骑士不能坐在圆桌的相邻位置。如果发生意见分歧，则需要举手表决，因此参加会议的骑士数目必须是大于 \(1\) 的奇数，以防止赞同和反对票一样多。知道骑士之间相互憎恨的关系后，请你帮忙统计有多少骑士参加不了任意一个会议。
输入格式
本题包含多组数据。
对于每组数据， 第一行为两个整数 \(n\) 和 \(m\)。
接下来 \(m\) 行每行两个整数 \(k_1\) 和 \(k_2\)，表示骑士 \(k_1\) 和 \(k_2\) 相互憎恨。
\(n=m=0\) 为数据末尾的标记，无需处理这组数据。
输出格式
对于每组数据，输出一行一个整数，表示无法参加任何会议的骑士数量。
感谢@hicc0305 提供的翻译
数据范围与提示
\(1\leq n \leq 10^3\)，\(1\leq m\leq10^6\)。保证 \(1\leq k_1,k_2\leq n\)。
\(\small{\text{Statement fixed by @Starrykiller.}}\)
我们考虑先建补图，那么我们就要求每个骑士都至少在一个奇环（点数为奇数）中。
那么怎么样判断是否在奇环中呢？我们有一个结论：
一个vdcc如果存在奇环，那么这个vdcc内的每个点都在一个奇环上 。
于是我们使用二分图染色对每个vdcc判奇环
/*
Keyblinds Guide
###################
@Ntsc 2024
- Ctrl+Alt+G then P : Enter luogu problem details
- Ctrl+Alt+B : Run all cases in CPH
- ctrl+D : choose this and dump to the next
- ctrl+Shift+L : choose all like this
- ctrl+K then ctrl+W: close all
- Alt+la/ra : move mouse to pre/nxt pos'
*/
#include <bits/stdc++.h>
#include <queue>
using namespace std;
#define rep(i, l, r) for (int i = l, END##i = r; i <= END##i; ++i)
#define per(i, r, l) for (int i = r, END##i = l; i >= END##i; --i)
#define pb push_back
#define mp make_pair
#define int long long
#define ull unsigned long long
#define pii pair<int, int>
#define ps second
#define pf first
// #define innt int
#define itn int
// #define inr intw
// #define mian main
// #define iont int
#define rd read()
int read(){
int xx = 0, ff = 1;
char ch = getchar();
while (ch < '0' || ch > '9') {
if (ch == '-')
ff = -1;
ch = getchar();
}
while (ch >= '0' && ch <= '9')
xx = xx * 10 + (ch - '0'), ch = getchar();
return xx * ff;
}
void write(int out) {
if (out < 0)
putchar('-'), out = -out;
if (out > 9)
write(out / 10);
putchar(out % 10 + '0');
}
#define ell dbg('\n')
const char el='\n';
const bool enable_dbg = 1;
template <typename T,typename... Args>
void dbg(T s,Args... args) {
if constexpr (enable_dbg){
cerr << s;
if(1)cerr<<' ';
if constexpr (sizeof...(Args))
dbg(args...);
}
}
#define zerol = 1
#ifdef zerol
#define cdbg(x...) do { cerr << #x << " -> "; err(x); } while (0)
void err() { cerr << endl; }
template<template<typename...> class T, typename t, typename... A>
void err(T<t> a, A... x) { for (auto v: a) cerr << v << ' '; err(x...); }
template<typename T, typename... A>
void err(T a, A... x) { cerr << a << ' '; err(x...); }
#else
#define dbg(...)
#endif
const int N = 2e3 + 5;
const int INF = 1e3;
const int M = 200;
const int MOD = 1e9 + 7;
vector<int> e[N];
void add(int a,int b){
e[a].pb(b);
e[b].pb(a);
}
int dfn[N],low[N];
int tim;
int stk[N],top;
bitset<N> vis,flg,col;
vector<int> ans[N];
int vdcc;
int res;
void tarjan(int x,int fa){
dfn[x]=low[x]=++tim;
stk[++top]=x;
int son=0;
for(auto v:e[x]){
if(v==fa)continue;
if(!dfn[v]){
son++;
tarjan(v,x);
low[x]=min(low[x],low[v]);
if(low[v]>=dfn[x]){
vdcc++;
int y;
do{
y=stk[top--];
ans[vdcc].pb(y);
}while(y!=v);//!!
ans[vdcc].pb(x);
}
}else low[x]=min(low[x],dfn[v]);
}
if(!(fa||son))ans[++vdcc].pb(x);
}
queue<int> q;
bool bfs(int s){
q.push(s);
vis[s]=1;
while(q.size()){
int x=q.front();
// cdbg(x);
q.pop();
for(auto v:e[x]){
if(!flg[v])continue;
if(vis[v]){
if(col[x]==col[v])return 0;
continue;
}
col[v]=col[x]^1;
vis[v]=1;
q.push(v);
}
}
return 1;
}
bool d[N][N];
bitset<N> able;
int n,m;
void init(){
for(int i=1;i<=n;i++){
while(e[i].size())e[i].pop_back();
}
memset(d,0,sizeof d);
memset(dfn,0,sizeof dfn);
memset(low,0,sizeof low);
tim=0;
top=0;
for(int i=1;i<=vdcc;i++){
while(ans[i].size())ans[i].pop_back();
}
vdcc=0;
}
void solve(){
init();
n=rd,m=rd;
if(n+m==0)exit(0);
for(int i=1;i<=m;i++){
d[rd][rd]=1;
}
for(int i=1;i<=n;i++){
for(int j=i+1;j<=n;j++){
if(!d[i][j]&&!d[j][i])add(i,j);
}
}
//判断一个点是否在一个奇数环内
//结论：一个vdcc如果存在奇环，那么这个vdcc内的每个点都在一个奇环上
//使用二分图染色判奇环
// cdbg("OK");
for(int i=1;i<=n;i++){
if(!dfn[i]){
tarjan(i,0);
}
}
// for(int i=1;i<=vdcc;i++){
// for(auto v:ans[i])dbg(v);
// ell;
// }
able.reset();
for(int i=1;i<=vdcc;i++){
for(auto v:ans[i])flg[v]=1;
if(bfs(ans[i].front())){
// res+=ans[i].size();
// cdbg("ban",i);
}else{
for(auto v:ans[i])able[v]=1;
}
for(auto v:ans[i])flg[v]=0,vis[v]=0;
}
res=0;
for(int i=1;i<=n;i++)res+=(able[i]==0);
cout<<res<<endl;
}
signed main() {
// freopen("P2619_3.in","r",stdin);
// freopen("center.out","w",stdout);
int T=1;
while(T){
solve();
}
return 0;
}