图论_连通_连通分量
- 格式：pdf
- 大小：89.76 KB
- 文档页数：4
图论_连通_连通分量
强连通图 : 强连通分量就是本⾝
有向图 --->
⾮强连通图 : 多个强连通分量
图--->
连通图 : 连通分量就是本⾝
⽆向图 --->
⾮连通图 : 多个连通分量
路径 : 顾名思义.
路径长度 : 路径上边的数量.
路径 : 顾名思义.
路径长度 : 路径上边的数量.
连通 : ⽆向图顶点A可以到顶点B,则称A,B连通.
强连通 : 有向图中，两个顶点间⾄少存在⼀条互相可达路径，则两个顶点强连通
连通图 : 图中任意两点都连通的图.
强连通图 : 有向图的任意两点都强连通.
连通分量 : ⽆向图的极⼤连通⼦图称为连通分量.连通图只有⼀个连通分量,即⾃⾝
强连通分量: 强连通图有向图的极⼤强连通⼦图.强连通图的强连通分量只有⼀个,即强连通图本⾝.
基图 : 将有向图的所有边替换成⽆向边形成的图.
弱连通图 : 基图是连通图的有向图.(即,连通的有向图)
求图的连通分量的⽬的，
是为了确定从图中的⼀个顶点是否能到达图中的另⼀个顶点，
也就是说，
图中任意两个顶点之间是否有路径可达。
求强连通分量有多种算法.
我⽤的Tarjan算法. 复杂度O(V+E)
这两个博客写得不错:
https://www.cnblogs.com/reddest/p/5932153.html https://www.cnblogs.com/shadowland/p/5872257.html
int dfn[16]; // 时间戳
int dfn_num = 0; // 时间
int low[16]; // 节点u所能访问到的最⼩时间戳
int inSt[16]; // 节点u是否在栈中.
int st[16];
int top = 0;
// 我们维护的信息.
int col[16]; // 给节点染⾊, 同⼀个连通块的节点应该是同⼀个颜⾊的.
int col_num = 0; // 颜⾊值.
int size[16]; // 每个颜⾊值所拥有的块数.
/*
第⼀步: 访问当前节点的所有⼦节点: ⼦节点有三种 第⼀种: 未访问过的, 我们对它进⾏访问, 同时设置它的时间戳dfn[u]和low[u]为++ndfn_num,以及进栈.
第⼆种: 访问过的,并且在栈中,我们直接更新我们 当前 节点的low[] --> 注意 应该⽤low[u] 和 dfn[v]⽐较.
第三种: 访问过的,并且不在栈中的, 我们直接跳过.因为这个时候,所以它已经染⾊了,属于⼀个连通块了.
第⼆步: 如果dfn[u] == low[u] 说明 已经找到⼀个连通块了. 这时候我们要将栈顶元素弹出,直到当前节点. 记得也要修改inSt, 同时维护我们需要的信息.
*/
void Tarjan(int u) {
int v, i; dfn[u] = low[u] = ++dfn_num; //添加时间戳.
st[++top] = u; // 进栈
inSt[u] = true; // 标⽰在栈
for (i=head[u]; i; i=edge[i].lst) {
v = edge[i].to;
if (!dfn[v]) {
Tarjan(v);
low[u] = min(low[u], low[v]);
} else if (inSt[v]) {
low[u] = min(low[u], dfn[v]);
}
}
if (dfn[u] == low[u]) {
col_num++;
do {
inSt[st[top]] = false;
col[st[top]] = col_num;
size[col_num]++;
} while (st[top--] != u);
}
}
View Code
加上2个板⼦题.
http://codevs.cn/problem/1332/
题⽬很简单: 要你求出最⼤的强连通块,如果有多个则输出字典序最⼩的⼀个.
#include
#include
#include
using namespace std;
const int maxn = 5e4+500;
struct Edge {
int lst;
int to;
}edge[maxn<<1];
int head[maxn];
int qsz = 1;
inline void add(int u, int v) {
edge[qsz].lst = head[u];
edge[qsz].to = v;
head[u] = qsz++;
}
int dfn[maxn]; // 时间戳
int dfn_num = 0; // 时间
int low[maxn]; // 节点u所能访问到的最⼩时间戳
int inSt[maxn]; // 节点u是否在栈中.
int st[maxn];
int top = 0;
// 我们维护的信息.
int col[maxn]; // 给节点染⾊, 同⼀个连通块的节点应该是同⼀个颜⾊的.
int col_num = 0; // 颜⾊值.
int size[maxn]; // 每个颜⾊值所拥有的块数.
int id[maxn];
void Tarjan(int u) {
int v, i;
dfn[u] = low[u] = ++dfn_num; //添加时间戳.
st[++top] = u; // 进栈
inSt[u] = true; // 标⽰在栈
for (i=head[u]; i; i=edge[i].lst) {
v = edge[i].to;
if (!dfn[v]) {
Tarjan(v);
low[u] = min(low[u], low[v]);
} else if (inSt[v]) {
low[u] = min(low[u], dfn[v]);
}
}
if (dfn[u] == low[u]) { col_num++;
id[col_num] = u;
do {
inSt[st[top]] = false;
col[st[top]] = col_num;
size[col_num]++;
id[col_num] = min(id[col_num], st[top]);
} while (st[top--] != u);
}
}
int main()
{
memset(id, 0x3f, sizeof(id));
int n, i, u, v, m, t;
scanf("%d%d", &n, &m);
for (i=1; i<=m; ++i) {
scanf("%d%d%d", &u, &v, &t);
add(u, v);
if (t==2) add(v, u);
}
for (i=1; i<=n; ++i)
if (!dfn[i]) Tarjan(i);
int mm = 0, tcol = -1;
for (i=1; i<=col_num; ++i)
if (mm < size[i]) {
mm = size[i];
tcol = i;
} else if (m == size[i]) {
if (id[tcol] > id[i])
tcol = i;
}
// printf("%d \n", tcol);
printf("%d\n", mm);
for (i=1; i<=n; ++i)
if (col[i] == tcol) printf("%d ", i);
printf("\n");
return 0;
}
View Code
https://vjudge.net/problem/HYSBZ-1051
题⽬: 求出所有⽜都欢迎的⽜的个数. 我们可以把所有连通块求出,然后把⼀个连通块看成⼀个点,即缩点. 然后找到出度为零的点(连通块), 如
果有且只有⼀个,那么连通块的点数就是答案,否则答案为零.
#include
#include
using namespace std;
struct Edge {
int lst;
int to;
}edge[50500];
int head[10100];
int qsz = 1;
inline void add(int u, int v) {
edge[qsz].lst = head[u];
edge[qsz].to = v;
head[u] = qsz++;
}
int dfn[10100]; // 时间戳
int dfn_num = 0; // 时间
int low[10100]; // 节点u所能访问到的最⼩时间戳
int inSt[10100]; // 节点u是否在栈中.
int st[10100];
int top = 0;
// 我们维护的信息.
int col[10100]; // 给节点染⾊, 同⼀个连通块的节点应该是同⼀个颜⾊的.
