图论_连通_连通分量 强连通图 : 强连通分量就是本⾝ 有向图 ---> ⾮强连通图 : 多个强连通分量图---> 连通图 : 连通分量就是本⾝ ⽆向图 ---> ⾮连通图 : 多个连通分量路径 : 顾名思义.路径长度 : 路径上边的数量.路径 : 顾名思义.路径长度 : 路径上边的数量.连通 : ⽆向图顶点A可以到顶点B,则称A,B连通.强连通 : 有向图中，两个顶点间⾄少存在⼀条互相可达路径，则两个顶点强连通连通图 : 图中任意两点都连通的图.强连通图 : 有向图的任意两点都强连通.连通分量 : ⽆向图的极⼤连通⼦图称为连通分量.连通图只有⼀个连通分量,即⾃⾝强连通分量: 强连通图有向图的极⼤强连通⼦图.强连通图的强连通分量只有⼀个,即强连通图本⾝.基图 : 将有向图的所有边替换成⽆向边形成的图.弱连通图 : 基图是连通图的有向图.(即,连通的有向图)求图的连通分量的⽬的，是为了确定从图中的⼀个顶点是否能到达图中的另⼀个顶点，也就是说，图中任意两个顶点之间是否有路径可达。
求强连通分量有多种算法.我⽤的Tarjan算法. 复杂度O(V+E)这两个博客写得不错:https:///reddest/p/5932153.htmlhttps:///shadowland/p/5872257.htmlint 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个板⼦题./problem/1332/题⽬很简单: 要你求出最⼤的强连通块,如果有多个则输出字典序最⼩的⼀个.#include <cstdio>#include <cstring>#include <algorithm>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");return0;}View Codehttps:///problem/HYSBZ-1051题⽬: 求出所有⽜都欢迎的⽜的个数. 我们可以把所有连通块求出,然后把⼀个连通块看成⼀个点,即缩点. 然后找到出度为零的点(连通块), 如果有且只有⼀个,那么连通块的点数就是答案,否则答案为零.#include <cstdio>#include <algorithm>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]; // 给节点染⾊, 同⼀个连通块的节点应该是同⼀个颜⾊的.int col_num = 0; // 颜⾊值.int size[10100]; // 每个颜⾊值所拥有的块数./*第⼀步: 访问当前节点的所有⼦节点: ⼦节点有三种第⼀种: 未访问过的, 我们对它进⾏访问, 同时设置它的时间戳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);}}bool ou[10010];int main(){// freopen("E:\\input.txt", "r", stdin);int n, i, j, u, v, m;scanf("%d%d", &n, &m);for (i=1; i<=m; ++i) {scanf("%d%d", &u, &v);add(u, v);}for (i=1; i<=n; ++i)if (!dfn[i])Tarjan(i);// 缩点操作int cnt = 0, res = 0;for (i=1; i<=n; ++i) {if (ou[col[i]]) continue;for (j=head[i]; j; j=edge[j].lst) {v = edge[j].to;if (col[i] != col[v]) {ou[col[i]] = true;break;}}}for (i=1; i<=col_num; ++i) {if (!ou[i]) {res = size[i];cnt++;}if (cnt > 1) {res = 0;break;}}printf("%d\n", res);return0;}View Code。
