点个赞❤️吧呜呜呜~ 写了好久呢, 虽然是给自己看的hh
补的博客
强连通分量 SCC
无向图的连通性问题
点双连通
在无向图中, 删除一个点(不是x或y)后， 点x和点y仍然能够彼此到达, 那么称x和y的点双连通的;
边双连通
在无向图中, 删除一条边后, 点x和点y仍然能够彼此到达, 那么称x和y是双连通的(所以x和y一定在一个环里);
性质: 点双连通不具有传递性, 但是边双连通具有传递性
什么是传递性? 例如x和y是边双连通 y和z是边双连通, 则x和z也是边双连通
一个环只删除一条边无法破坏它的连通性
下面的例子给出了点双连通为什么没有传递性
图没画好有红X的那个点是y
割点(割顶)
在无向图G中, 若删除x后, 连通块的数量增加, 则称x为无向图G中的一个割点(割顶)
一个n个点的图最多有n-2个割点(就是一条链)
性质: 至少有3个点的无向图, 才可能存在割点
2个点的, 很水吧
dfn[u]:到u节点的时间戳
时间戳:dfs序的时间单位遍历
low[u]:表示u节点能到达的最小时间戳
割点的判定:
若搜索树中, 有从x到y的连边, 当$\text{low}[y] \geq \text{dfn}[x]$时说明y能到达的最小时间戳在x的时间戳之上, y被x与x之前的节点“隔开”, x 可能 是割点
只要x不是搜索树的根节点，或者x是根节点, 但是子节点大于1个, 那么x就是割点.
注意!!! 图可能不连通
void tarjan(int u)
{
dfn[u] = low[u] = ++timestamp; // 打时间戳
int cnt = 0; // 统计u有几个子节点
for (int i = h[u]; ~i; i = ne[i])
{
int j = e[i];
if (!dfn[j]) // y没去过
{
tarjan(j); // 递归继续搜索
low[u] = min(low[u], low[j]); // 维护u能到达的最小时间戳 low[u]
if (low[j] >= dfn[u]) // u可能是根节点
{
cnt++; // j没有去过, 说明j是u在当前搜索树中的一个子节点
if (u != root || cnt > 1) // 排除根节点且只有一个子节点的情形
{
cut += !st[u];
st[u] = true;
}
}
}
else // j去过, 所以j还没有回溯, 不能用low[j]
low[u] = min(low[u], dfn[j]);
}
}
P3388 【模板】割点（割顶）
模板题很水的, 就是要注意图有可能不连通(题目也说了的)
Tourist Guide
很水用map统计字符串即可, 就是要注意UVA每次除了第一次以外要多输出一个换行(样例是真特殊…)
System Administrator
题意:构造n个点m条边的无向连通图, 且无重边, 点v必须是割点, 特判无解
1. 有解时, m有一定下界和上界, 下界$m≥n-1$
2. j已经连了n-1个点, 不能有重边, 因此j不能再连边, 视为j不存在;
3. 为了保证容纳的边尽量可能多, 要尽量连完全图, 且不能破坏j的割点特征;
4. 留一个单点只跟j保持连边, 剩下的n-2个点构造完全图即可;
5. 上界 边数=n - 1 + (n - 2) * (n - 3) / 2
#include <bits/stdc++.h>
using namespace std;
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n, m, v;
cin >> n >> m >> v;
if (m < n - 1 || m > (n - 1) * (n - 2) / 2 + 1) cout << -1;
else
{
m -= n - 1;
for (int i = 1; i <= n; i++)
if (i != v) cout << v << ' ' << i << '\n';
if (m)
{
for (int i = 2; i < n; i++)
if (i != v)
for (int j = 1; j < i; j++)
if (j != v)
{
cout << i << ' ' << j << '\n';
m--;
if (!m) return 0;
}
}
}
return 0;
}
Tourist Guide
一个点 $i$,如果是不是割点, 那么贡献一定是 $\lfloor \frac{n - 2} {2} \rfloor$;
否则根据容斥原理, 贡献是 $(n-1)+\sum_{y = A_i}{\left(y \times (n-y)\right)}+(z+1)\times(n-z-1)$.
其中 $A_i$ 为节点 $i$ 满足：$i$ 是 $x$ 的子节点,$i$ 之前没有访问过且 $low_i >= dfn_x$, $z$ 为 $\sum a_i$.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5 + 10, M = 1e6 + 10;
int h[N], e[M], ne[M], idx;
int dfn[N], low[N];
bool st[N];
ll s[N], f[N];
int timestamp;
int root;
int n, m;
void add(int a, int b)
{
e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}
void tarjan(int u)
{
s[u] = 1;
dfn[u] = low[u] = ++timestamp;
int cnt = 0;
ll sum = 0;
for (int i = h[u]; ~i; i = ne[i])
{
int j = e[i];
if (!dfn[j])
{
tarjan(j);
s[u] += s[j];
low[u] = min(low[u], low[j]);
if (low[j] >= dfn[u])
{
f[u] += s[j] * (n - s[j]);
sum += s[j];
cnt++;
if (u != root || cnt > 1) st[u] = true;
}
}
else
low[u] = min(low[u], dfn[j]);
}
if (!st[u]) f[u] = 2 * (n - 1);
else f[u] += (n - sum - 1) * (sum + 1) + (n - 1);
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> n >> m;
memset(h, -1, sizeof h);
int a, b;
while (m--)
{
cin >> a >> b;
add(a, b);
add(b, a);
}
for (int i = 1; i <= n; i++)
if (!dfn[i])
{
root = i;
tarjan(i);
}
for (int i = 1; i <= n; i++) cout << f[i] << '\n';
return 0;
}
Make It Connected CF1761E
题意:给定一个无向图, 每次选择一个点u, 和j(1 <= j <= n, j != u) 若点u与点j有连边删除连边, 反之加上连边
#include <bits/stdc++.h>
using namespace std;
const int N = 4010;
string s[N];
bool st[N];
int d[N];
int n;
void dfs(int u, vector<int> &g)
{
st[u] = true;
g.push_back(u);
for (int i = 1; i <= n; i++)
if (!st[i] && s[u - 1][i - 1] == '1') dfs(i, g);
}
void meow_meow()
{
vector<vector<int>> g;
for (int i = 1; i <= n; i++)
if (!st[i])
{
vector<int> now;
dfs(i, now);
int m = (int)now.size();
if (m == n)
{
cout << "0\n";
return;
}
if (m == 1)
{
cout << "1\n";
cout << now[0] << '\n';
return;
}
int k = now[0];
for (auto i : now)
if (d[i] < d[k]) k = i;
if (d[k] < m - 1)
{
cout << "1\n";
cout << k << '\n';
return;
}
g.push_back(now);
}
if (g.size() > 2)
{
cout << "2\n";
cout << g[0][0] << ' ' << g[1][0] << '\n';
}
else if (g[0].size() < g[1].size())
{
cout << g[0].size() << '\n';
for (auto i : g[0]) cout << i << ' ';
cout << '\n';
}
else
{
cout << g[1].size() << '\n';
for (auto i : g[1]) cout << i << ' ';
cout << '\n';
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int t;
cin >> t;
while (t--)
{
cin >> n;
for (int i = 1; i <= n; i++) st[i] = false, d[i] = 0;
for (int i = 0; i < n; i++)
{
cin >> s[i];
for (auto j : s[i])
if (j == '1') d[i + 1]++;
}
meow_meow();
}
return 0;
}
割边
一个无向图中, 若删除一条边连通块的数量增加, 则这条边为割边
割边的判定
若low[j] > dfn[u], 则边(u, j)为割边
很好理解的更前面的差不多
割边例题
void tarjan(int u, int p)
{
dfn[u] = low[u] = ++timestamp;
for (int i = h[u]; ~i; i = ne[i])
{
int j = e[i];
if (!dfn[j])
{
tarjan(j, u);
low[u] = min(low[u], low[j]);
if (low[j] > dfn[u]) cnt++;
}
else if (j != p)
low[u] = min(low[u], dfn[j]);
}
}
P7687 [CEOI2005] Critical Network Lines
题意:无向图, 有K个A类点, L个B类点, 可重叠.
要求N个点访问A和B类服务, 求关键边.
1. 初始时, 所有点访问A和B类服务;
2. 如果一条边, 非割边, 以为在环上, 伤处后不改变连通性不可能是关键边;
3. 关键边应该是割边的一个子集;
4. 对于(x, y)的连边, 两侧不能出现没有A或者没有B类服务的点;
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> PII;
const int N = 1e5 + 10, M = 2e6 + 10;
int h[N], e[M], ne[M], idx;
int dfn[N], low[N], timestamp;
int a[N], b[N];
vector<PII> g;
int n, m, k, l;
void add(int a, int b)
{
e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}
void tarjan(int u, int p)
{
low[u] = dfn[u] = ++timestamp;
for (int i = h[u]; ~i; i = ne[i])
{
int j = e[i];
if (!dfn[j])
{
tarjan(j, u);
low[u] = min(low[u], low[j]);
if (low[j] > dfn[u])
if (!a[j] || !b[j] || a[j] == k || b[j] == l)
g.push_back({j, u});
a[u] += a[j];
b[u] += b[j];
}
if (j != p)
low[u] = min(low[u], dfn[j]);
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> n >> m >> k >> l;
int v;
for (int i = 0; i < k; i++)
{
cin >> v;
a[v] = 1;
}
for (int i = 0; i < l; i++)
{
cin >> v;
b[v] = 1;
}
memset(h, -1, sizeof h);
int a, b;
while (m--)
{
cin >> a >> b;
add(a, b);
add(b, a);
}
tarjan(1, 0);
cout << g.size() << '\n';
for (auto i : g)
cout << i.first << ' ' << i.second << '\n';
return 0;
}
