图的连通性问题

参考资料：

　　[1]:挑战程序设计竞赛

　　[2]:深度优先生成树及其应用

　　[3]:算法笔记--强连通分量分解

　　[4]:数据结构中的图存储结构

　　[5]:网易有道笔试：求连通图的割点（关节点）

Kosaraju算法模板：

　　来自挑战程序设计竞赛

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<vector>
 5 using namespace std;
 6 #define pb push_back
 7 #define mem(a,b) memset(a,b,sizeof a)
 8 const int maxn=1e5+10;//最大的节点个数，一般是 1e5 级别的
 9 
10 int scc[maxn];//所属强连通分量的拓扑排序
11 bool vis[maxn];//vis[u] : dfs中判断节点u是否被访问过
12 vector<int >vs;//后序遍历顺序的顶点列表
13 vector<int >edge[maxn],redge[maxn];//边、反边
14 
15 void addEdge(int u,int v)
16 {
17     edge[u].pb(v);
18     redge[v].pb(u);
19 }
20 void Dfs(int u)//第一次dfs，后序遍历标记，越靠近叶子结点标号越小
21 {
22     vis[u]=true;
23     for(int i=0;i < edge[u].size();++i)
24     {
25         int to=edge[u][i];
26         if(!vis[to])
27             Dfs(to);
28     }
29     vs.pb(u);
30 }
31 void rDfs(int u,int sccId)//反向dfs，利用反向图，求出强连通分量个数
32 {
33     vis[u]=true;
34     scc[u]=sccId;
35     for(int i=0;i < redge[u].size();++i)
36     {
37         int to=redge[u][i];
38         if(!vis[to])
39             rDfs(to,sccId);
40     }
41 }
42 int Scc(int maxV)
43 {
44     mem(vis,false);
45     vs.clear();
46     for(int i=1;i <= maxV;++i)
47         if(!vis[i])
48             Dfs(i);
49     mem(vis,false);
50     int sccId=0;//DAG节点个数
51     for(int i=vs.size()-1;i >= 0;--i)
52     {
53         int to=vs[i];
54         if(!vis[to])
55         {
56             sccId++;
57             rDfs(to,sccId);
58         }
59     }
60     return sccId;//返回强连通分量的个数
61 }

View Code

题目一览表	来源	考察知识点	完成时间
A　　 2186 Popular Cows	poj	强连通分量入门题	2018.10.3
B　　 1236 Network of Schools	poj	强连通分量分解模板题	2018.10.3
C　　1904 King's Quest	poj	强连通分量+完美匹配	2018.10.3
D　　4685 Prince and Princess	hdu	强连通分量+完美匹配	2018.10.4