数据结构————图的连通性算法
相关概念
割点:无向连通图,删除这个点和这个点关联的边,图不连通
点双连通图:无向连通图,没有割点出现
桥:无向连通图,删除某条边,图不连通
边双连通图:无向连通图,没有桥
时间戳:对一个图做深度优先搜索的时候,第一次访问某个点的时间
强连通分量:有向图任意两点都可互相到达
求割点和点连通分量
int times = 0; |
//普通建图输出点霜 |
emm
例题
铁路
一直t不知道为啥
55看队长的题解
桥和边连通分量
int times = 0; |
例题
Redundant Paths
题意: 添加最少的边使这棵树上所有的链都变成环
缩点后是一棵树 贪心 注意重边标记
对于无向图的缩点,由于是无向图,所以要从u到v建一条边,又要从v到u建一条边,但是,在tarjan时会有两条边重复,这是一个麻烦,而且,还不得不建两条边,这该怎么办呢?
解决的方法就是,当同一条无向边的两条有向边的其中一条走过时,把另一条同时赋值为走过,这就要用到一个神奇的公式,^ 1。
举例来说,
0 ^ 1=1, 1 ^ 1=0;
2 ^ 1=3, 3 ^ 1=2;
4 ^ 1=5, 5 ^ 1=4;
而建边的时候,一条无向边的两条有向边刚好相差1
|
强连通分量
复杂度(V+E)
using namespace std;
const int maxm = 1010;
const int maxn = 110;
struct edge {
int v;
int next;
} E[maxm];
int p[maxn], eid = 0;
void init() {
memset(p, -1, sizeof(p));
eid = 0;
}
void insert(int u, int v) {
E[eid].v = v;
E[eid].next = p[u];
p[u] = eid++;
}
int times = 0;
int dfn[maxn], low[maxn];
int scc_cnt = 0; // 强连通分量数量
int sccno[maxn]; // 记录每个点属于的强连通分量的编号
set<int> scc[maxn];
stack<int> S;// 把点压入栈中 因为每个点只属于一个强连通分量
void dfs (int u) {
dfn[u] = low[u] = ++times;
S.push(u);
for (int i = p[u]; i != -1; i = E[i].next) {
int v = E[i].v;
if (dfn[v] == 0) { // v 没有被访问过,u, v 是树边
dfs(v);
low[u] = min(low[u], low[v]);
} else if (!sccno[v]) { // 对于已经求出 scc 的点,直接删除
low[u] = min(low[u], dfn[v]);
}
}
if (low[u] == dfn[u]) { // 说明 u 是第一个被探测到的点
++scc_cnt;
while (true) {
int x = S.top();
S.pop();
sccno[x] = scc_cnt;// 记录这个点在哪个连通分量
scc[scc_cnt].insert(x);
if (x == u) {
break;
}
}
}
}
/*缩点
edge new_E[maxm];
int new_p[maxn], new_eid=0;
void new_init() {
memset(new_p, -1, sizeof(new_p));
new_eid=0;
}
void new_insert(int u, int v) {
new_E[new_eid].v=v;
new_E[new_eid].next=new_p[u];
new_p[u]=new_eid++;
}*/
int main() {
init();
int n, m;
cin >> n >> m;
for (int i = 0; i < m; ++i) {
int u, v;
cin >> u >> v;
insert(u, v);
}
memset(dfn, 0, sizeof(dfn));
memset(sccno, 0, sizeof(sccno));
times = scc_cnt = 0;
for (int i = 1; i <= n; ++i) {
if (!dfn[i]) { // 每个点都要尝试 dfs 一次
dfs(i);
}
}
/* 缩点
new_init();
for(int u=1; u<=n; ++u) {
for(int i=p[u]; i!=-1; i=E[i].next) {
int v=E[i].v;
if(sccno[u]!=sccno[v]) {
new_insert(sccno[u], sccno[v]);
}
}
}
*/
cout << scc_cnt << endl;
for (int i = 1; i <= scc_cnt; ++i) {
for (set<int>::iterator it = scc[i].begin(); it != scc[i].end(); ++it) {
cout << (*it) << " ";// 输出连通分量
}
cout << endl;
}
return 0;
}
例题
迷宫
裸板子判断是不是强连通图
炸弹
本来想用并查集但是情况复杂的多
学校
题意:添加尽可能少的边使新图强连通:
我们先求出强连通分量,然后缩点得到一个DAG,假设新图上有a个结点的入度为0,有b个节点的出度为0,ans=max(a, b)(出度为0的点连入入度为0的点);
特殊情况:原图本身是强连通的时候答案是0不是1
欧拉回路
最小树形图
<hr style=” border:solid; width:100px; height:1px;” color=#000000 size=1”>
总结
bshd
看题面不知道怎么转化成图的连通性问题 板子也不熟