算法系列札记6(有关图的算法一—搜索，拓扑排序和强连通分支) - 编程当前位置:& &&&算法系列札记6(有关图的算法一—搜索，拓扑排序和强算法系列札记6(有关图的算法一—搜索，拓扑排序和强连通分支)&&网友分享于：&&浏览：0次算法系列笔记6(有关图的算法一—搜索，拓扑排序和强连通分支)简单概念：对于图G(V,E)，通常有两种存储的数据结构，一种是邻接矩阵，此时所需要的存储空间为O(V^2)；第二种是邻接表，所需要的存储空间为O(V+E)。邻接表表示法存在很强的适应性，但是也有潜在的不足，当要快速的确定图中边(u,v)是否存在，只能在顶点u的邻接表中搜索v，没有更快的方法，此时就可以使用邻接矩阵，但要以占用更多的存储空间作为代价；此外当图不是加权的，采用邻接矩阵存储还有一个优势：在存储邻接矩阵的每个元素时，可以只用一个二进位，而不必用一个字的空间。
图的搜索算法
搜索一个图示有序地沿着图的边访问所有的顶点，主要有两种搜索算法，广度优先遍历(bfs，也称为宽度遍历)和深度优先遍历(dfs)。
广度优先(bfs)
从源点s对图进行广度优先遍历，得到的路径为从源点s到其它各点的最短路径，也生成了一棵广度优先树。广度优先遍历需要一个队列，先进先出。
代码如下：
// 广度遍历图
void Graph::bfs(int s){
queue&int&
q.push(s);
visited[s] = 1;
while(!q.empty()){
int u = q.front();
cout && u &&& &;
GNode *p = edges[u].
while(p != NULL){
if(!visited[p-&val]){
// 未被访问，则将其加入队列中并标志为访问过
q.push(p-&val);
visited[p-&val] = 1;
void Graph::bfsTravel(){
memset(visited, 0, sizeof(int)*vertexNum);
for(int i = 0; i & vertexN i++){
if(!visited[i]){
时间复杂度为O(V+E)
深度优先(dfs)
深度优先搜素形成了一个由数棵深度优先树所组成的深度优先森林，每条边被称为树边。此外深度遍历对于每个节点会有个时间戳，用于标识该结点开始访问和结束访问的时间。一个重要的特性就是发现和完成时间具有括号结构。
代码如下：
// 深度优先遍历
void Graph::dfs(int s){
visited[s] = 1;
time += 1;
beginTime[s] =
cout && s && &(& && beginTime[s] && & &;
GNode *p = edges[s].
while(p != NULL){
if(!visited[p-&val])
dfs(p-&val);
time += 1;
endTime[s] =
topSort.push_back(s);
cout && endTime[s] && &)& &&& &;
void Graph::dfsTravel(){
memset(visited, 0, sizeof(int)*vertexNum);
memset(beginTime, 0, sizeof(int)*vertexNum);
// 结点开始访问的时间
memset(endTime, 0, sizeof(int)*vertexNum);
// 结点结束访问的时间
for(int i = 0; i & vertexN i++){
if(!visited[i]){
时间复杂度O(V+E)
对于深度优先遍历，其边还可以划分为4类。
(1)树边，深度遍历森林中的每条边就是树边。
(2)前向边，u到其后裔的非树边(u,v)。
(3)反向边，u到其祖先的边(u,v)。
(4)横向边，一个顶点就不是另外一个顶点的祖先或者后裔。
性质：(1)一个有向图是无回路的，当且仅当对该图的深度优先搜索没有产生反向边
(2)对一个无向图G进行深度优先搜索的过程中，G的每一条边要么是树边，要么是反向边。
有向无回路图(DAG,directed acyclic graph)的拓扑排序是深度优先搜索的一个应用。拓扑排序是对图G的所有顶点的一个线性序列，如果对于图G中的边(u,v)，则顶点u排在顶点v的前面。在很多应用中，有向无回路图用于说明事件发生的先后次序。
算法基本思想：通过对DAG图进行深度优先遍历以得到完成访问每个结点的时间，其逆序就是DAG图的拓扑排序。
代码如下：已经在深度遍历中体现。
时间复杂度为O(V+E)。
强连通分支
强连通分支为深度优先搜索的另一个经典应用。有向图G=(V,E)的一个强连通分支就是一个最大顶点C是V的子集，使得C中任意两个顶点可以相互到达
图G的转置：GT=(V,ET),ET={(u,v):(u,v) ∈E}.由ET是由G的边改变方向后所组成的。建立GT所需要的时间复杂度也为O（V+E）
算法的基本思想：首先对图G进行深度优先搜索，据此得到图G的拓扑排序序列，然后将图GT按照此序列进行深度遍历，得到的括号结构便是所有的强连通分支。时间复杂度仍然为O(V+E)
代码如下：
// 创建图g的转置
void Graph::buildTransGraph(Graph &g){
this-&vertexNum = g.vertexN
this-&edgesNum = g.edgesN
for(int i = 0; i & vertexN i++){
this-&vertex[i] = g.vertex[i];
this-&edges[i].val = g.edges[i].
this-&edges[i].weight = g.edges[i].
this-&edges[i].next = NULL;
for(int i = 0; i & vertexN i++){
GNode *p = g.edges[i].
while(p != NULL){
GNode *newNode = new GNode();
newNode-&val =
newNode-&next = NULL;
newNode-&weight = p-&
GNode *q = &edges[p-&val];
while(q-&next != NULL) q = q-&
q-&next = newN
//强连通分量
void Graph::componentSC(){
//time = 0;
//dfsTravel();
// 对图g进行深度搜索得到完成x访问所需要的时间 并由此得到其拓扑排序
g2.buildTransGraph(*this);
// 得到图G的转置
memset(g2.visited, 0, sizeof(int)*vertexNum);
cout && &强连通分量: & &&
for(vector&int&::reverse_iterator iter = topSort.rbegin(); iter != topSort.rend(); iter++){
// 对转置图g2进行深度搜索得到强连通分量
if(!g2.visited[*iter])
g2.dfs(*iter);
完整代码：
#ifndef GRAPH_H
#define GRAPH_H
#include &iostream&
#include &vector&
#define maxSize 10
#define maxInt 0x
// 将此值设为权值的最大值
struct GNode{
class Graph{
void createGraph(int n, int e);
void destroyGraph(GNode *p);
for(int i = 0; i & vertexN i++){
destroyGraph(edges[i].next);
//cout && &析构:& && i &&
void showGraph();
void bfsTravel();
// 广度遍历
void dfsTravel();
// 深度遍历
void showTopSort();
输出拓扑序列
void componentSC();
// 建立图g的强连通分量
void prim();
int vertex[maxSize];
// 存放顶点
GNode edges[maxSize];
存放邻接表
int vertexN
//顶点个数
int edgesN
//bfs and dfs 遍历
int visited[maxSize];
void bfs(int s);
void dfs(int s);
int beginTime[maxSize];
// 深度开始访问x的时间
int endTime[maxSize];
// 结束访问x的时间
vector&int& topS
// topSort的逆序为有向无回路的拓扑排序
void buildTransGraph(Graph &g);
// 建立图g的转置
int lowcost[maxSize];
#include &iostream&
#include &graph.h&
#include &queue&
int Graph::time = 0;
void Graph::createGraph(int n, int e){
vertexNum =
edgesNum =
for(int i = 0; i & i++){
vertex[i] =
edges[i].val =
edges[i].weight = 0;
edges[i].next = NULL;
for(int i = 0; i & i++){
int source, dest,
cin && source && dest &&
GNode *newNode = new GNode();
newNode-&val =
newNode-&weight =
newNode -&next = NULL;
GNode *p = &edges[source];
while(p-&next != NULL) p = p-&
p-&next = newN
有向图就将这段删除掉
/*GNode *newNode2 = new GNode();
newNode2-&val =
newNode2-&weight =
newNode2 -&next = NULL;
GNode *p2 = &edges[dest];
while(p2-&next != NULL) p2 = p2-&
p2-&next = newNode2;*/
void Graph::destroyGraph(GNode *p){
if(p == NULL)
destroyGraph(p-&next);
void Graph::showGraph(){
for(int i = 0; i & vertexN i++){
cout && i && &-&&;
GNode *p = edges[j].
while( p != NULL) {
cout && &(& && p-&val &&&,& && p-&weight && &)& ;
// 广度遍历图
void Graph::bfs(int s){
queue&int&
q.push(s);
visited[s] = 1;
while(!q.empty()){
int u = q.front();
cout && u &&& &;
GNode *p = edges[u].
while(p != NULL){
if(!visited[p-&val]){
// 未被访问，则将其加入队列中并标志为访问过
q.push(p-&val);
visited[p-&val] = 1;
void Graph::bfsTravel(){
memset(visited, 0, sizeof(int)*vertexNum);
for(int i = 0; i & vertexN i++){
if(!visited[i]){
// 深度优先遍历
void Graph::dfs(int s){
visited[s] = 1;
time += 1;
beginTime[s] =
cout && s && &(& && beginTime[s] && & &;
GNode *p = edges[s].
while(p != NULL){
if(!visited[p-&val])
dfs(p-&val);
time += 1;
endTime[s] =
topSort.push_back(s);
cout && endTime[s] && &)& &&& &;
void Graph::dfsTravel(){
memset(visited, 0, sizeof(int)*vertexNum);
memset(beginTime, 0, sizeof(int)*vertexNum);
// 结点开始访问的时间
memset(endTime, 0, sizeof(int)*vertexNum);
// 结点结束访问的时间
for(int i = 0; i & vertexN i++){
if(!visited[i]){
输出拓扑排序
void Graph::showTopSort(){
for(vector&int&::reverse_iterator iter = topSort.rbegin(); iter != topSort.rend(); iter ++)
cout && *iter && & &;
// 创建图g的转置
void Graph::buildTransGraph(Graph &g){
this-&vertexNum = g.vertexN
this-&edgesNum = g.edgesN
for(int i = 0; i & vertexN i++){
this-&vertex[i] = g.vertex[i];
this-&edges[i].val = g.edges[i].
this-&edges[i].weight = g.edges[i].
this-&edges[i].next = NULL;
for(int i = 0; i & vertexN i++){
GNode *p = g.edges[i].
while(p != NULL){
GNode *newNode = new GNode();
newNode-&val =
newNode-&next = NULL;
newNode-&weight = p-&
GNode *q = &edges[p-&val];
while(q-&next != NULL) q = q-&
q-&next = newN
//强连通分量
void Graph::componentSC(){
//time = 0;
//dfsTravel();
// 对图g进行深度搜索得到完成x访问所需要的时间 并由此得到其拓扑排序
g2.buildTransGraph(*this);
// 得到图G的转置
memset(g2.visited, 0, sizeof(int)*vertexNum);
cout && &强连通分量: & &&
for(vector&int&::reverse_iterator iter = topSort.rbegin(); iter != topSort.rend(); iter++){
// 对转置图g2进行深度搜索得到强连通分量
if(!g2.visited[*iter])
g2.dfs(*iter);
#include &iostream&
#include &graph.h&
int main(){
g.createGraph(8, 13);
cout && &邻接表: & &&
g.showGraph();
cout && &广度遍历的结果: & &&
g.bfsTravel();
cout && &深度遍历的结果: & &&
具有括号结果
其中x(a b)
a代表开始访问x的时间
b代表完成访问x的时间
g.dfsTravel();
// 深度遍历完成访问x的时间的逆序就是有向无回路的拓扑排序
cout && &拓扑排序: & &&
g.showTopSort();
g.componentSC();
其中0(1 2(2 3) 4)表示在深度遍历中第0个结点开始访问结点的时间为1，结束访问结点的时间为4；2结点开始访问的时间为2，结束访问的时间为3.
12345678910
12345678910
12345678910 上一篇：下一篇：文章评论相关解决方案 1234567891011 Copyright & &&版权所有图的拓扑排序
转自：/xiaosuo/archive//1690302.html
　　对一个有向无环图(Directed Acyclic
Graph简称DAG)G进行拓扑排序，是将G中所有顶点排成一个线性序列，使得图中任意一对顶点u和v，若&u，v&
∈E(G)，则u在线性序列中出现在v之前。
&& 　通常，这样的线性序列称为满足拓扑次序(TopoiSicai
Order)的序列，简称拓扑序列。
　①若将图中顶点按拓扑次序排成一行，则图中所有的有向边均是从左指向右的。
　②若图中存在有向环，则不可能使顶点满足拓扑次序。
　③一个DAG的拓扑序列通常表示某种方案切实可行。
　【例】一本书的作者将书本中的各章节学习作为顶点，各章节的先学后修关系作为边，构成一个有向图。按有向图的拓扑次序安排章节，才能保证读者在学习某章节时，其预备知识已在前面的章节里介绍过。
&& 　④一个DAG可能有多个拓扑序列。
　【例】对图G9进行拓扑排序，至少可得到如下的两个(实际远不止两个)拓扑序列：C0，C1，C2，C4，C3，C5，C7，C8，C6和C0，C7，C9，C1，C4，C2，C3，C6，C5。
　　　　　　　　
　　⑤当有向图中存在有向环时，拓扑序列不存在
【例】下面(a)图中的有向环重排后如(b)所示，有向边&v3，vl&和其它边反向。若有向图被用来表示某项工程实施方案或某项工作计划，则找不到该图的拓扑序列(即含有向环)，就意味着该方案或计划是不可行的。
　　　　　　　　
二、无前趋的顶点优先的拓扑排序方法　　
　　该方法的每一步总是输出当前无前趋(即人度为零)的顶点，其抽象算法可描述为：
　　　　NonPreFirstTopSort(G){//优先输出无前趋的顶点
　　　　& while(G中有人度为0的顶点)do{
　　　　　　从G中选择一个人度为0的顶点v且输出之；
&&&&&　　　　&　　
从G中删去v及其所有出边；
&&&&&　　　　&&
&&&&　　　　&&&
if(输出的顶点数目&|V(G)|)
&&&&&　　　　&&&&&
& //若此条件不成立，则表示所有顶点均已输出，排序成功。
&&&&&&&　　　　　　Error("G中存在有向环，排序失败！")；
&&&&　　　　
　无前趋的顶点优先的拓扑排序算法在具体存储结构下，为便于考察每个顶点的人度，可保存各顶点当前的人度。为避免每次选入度为0的顶点时扫描整个存储空间，可设一个栈或队列暂存所有入度为零的顶点：
　在开始排序前，扫描对应的存储空间，将人度为零的顶点均入栈(队)。以后每次选人度为零的顶点时，只需做出栈(队)操作即可。
三、无后继的顶点优先拓扑排序方法　　
1、思想方法&&&
　该方法的每一步均是输出当前无后继(即出度为0)的顶点。对于一个DAG，按此方法输出的序列是逆拓扑次序。因此设置一个栈(或向量)T来保存输出的顶点序列，即可得到拓扑序列。若T是栈，则每当输出顶点时，只需做人栈操作，排序完成时将栈中顶点依次出栈即可得拓扑序列。若T是向量，则将输出的顶点从T[n-1]开始依次从后往前存放，即可保证T中存储的顶点是拓扑序列。
2、抽象算法描述
　　算法的抽象描述为：
　　NonSuccFirstTopSort(G){//优先输出无后继的顶点
while(G中有出度为0的顶点)do {
&&&&&　　&
从G中选一出度为0的顶点v且输出v；
&&&&　　&&
从G中删去v及v的所有人边
&&&&　　&&
if(输出的顶点数目&|V(G)|)
&&&&&　　&&&&&
Error("G中存在有向环，排序失败!")；
3、算法求精
　在对该算法求精时，可用逆邻接表作为G的存储结构。设置一个向量outdegree[0..n-1]或在逆邻接表的顶点表结点中增加1个出度域来保存各
顶点当前的出度；设置一个栈或队列来暂存所有出度为零的顶点。除了增加一个栈或向量T来保存输出的顶点序列外，该算法完全类似于
NonPreFirstTopSort。
四、利用深度优先遍历对DAG拓扑排序　　
　　当从某顶点v出发的DFS搜索完成时，v的所有后继必定均已被访问过(想像它们均已被删除)，此时的v相当于是无后继的顶点，因此在DFS算法返回之前输出顶点v即可得到
DAG的逆拓扑序列。
　其中第一个输出的顶点必是无后继(出度为0)的顶点，它应是拓扑序列的最后一个顶点。若希望得到的不是逆拓扑序列，同样可增加T来保存输出的顶点。若假设T是栈，并在DFSTraverse算法的开始处将T初始化，
&& 　利用DFS求拓扑序列的抽象算法可描述为：
& 　　　　void DFSTopSort(G，i，T){
　　　　//在DisTraverse中调用此算法，i是搜索的出发点，T是栈
&&&　　　　 int
&&&　　　　
visited[i]=TRUE； //访问i
&&&　　　　
for(所有i的邻接点j)//即&i，j&∈E(G)
&&&　　　　&&
if(!visited[j])
&&&&　　　　&&
DFSTopSort(G，j，T)；
&&&&　　　　&&
//以上语句完全类似于DFS算法
&&&&　　　　&
Push(&T，i)； //从i出发的搜索已完成，输出i
&&　　　　& }
　只要将深度优先遍历算法DFSTraverse中对DFS的调用改为对DFSTopSort的调用，即可求得拓扑序列T。其具体算法不难从上述抽象算法求精后得到。
若G是一个DAG，则用DFS遍历实现的拓扑排序与NonSuccFirstTopSort算法完全类似；但若C中存在有向环，则前者不能正常工作。
已投稿到：
以上网友发言只代表其个人观点，不代表新浪网的观点或立场。2171人阅读
算法导论相关（38）
半连通的定义，有向图G(V,E)，任意两个不同的点u、v，u有一条路径可达v或者v有一条路径可达u，从定义中可以看出，强连通图一定是半连通的。
引理：有向无环图G(V,E)，G是半连通的当且仅当有一条路径，这条路径上有图G中所有点。
证明：充分性很显然，如果有这样一条路径，则任意两个点之间都有一条路径。
必要性，有向无环图，可以对其进行拓扑排序得到一个拓扑序列，拓扑序列中任意两个相邻的结点u,v，由半连通的定义可知，要么v~u，要么u~v，以下为图G的拓扑序列。
.....u,v................
(1) v~u，即有一条v到u的路径，而根据拓扑排序的属性，任意一条边只能从左边到右边，故从v无论如何都不能到达u
(2)u~v，即有一条从u到v的路径，如果没有边(u,v)，u只能指向v之后的结点，根据拓扑排序的属性，任意一条边只能从左边到右边，故u不到达到v与半连通矛盾，故一定存在边(u,v)。
与是拓扑序列的任意两个相邻结点之间均有边，则这个拓扑序列就是这样的一条路径，其中包含图G的所有结点。
对于任意图G，只需要将其转化为有向无环图(DAG)，即通过强连通分支算法获取图G的连通分支图GSCC，分支图GSCC一定是有向无环图，故可以使用引理来确定是否为半连通。使用kosaraju 算法，因为此算法第二次DFS正好得到GSCC的拓扑序列，然后只要验证相邻的结点是否均有边即可。
* 以上用户言论只代表其个人观点，不代表CSDN网站的观点或立场
访问：60429次
积分：1213
积分：1213
排名：千里之外
原创：64篇
评论：11条
(1)(1)(2)(1)(1)(2)(3)(2)(7)(8)(3)(14)(9)(2)(9)&&&& &&&&&&
&& &&&&&&&&&&&&&&
鲁ICP备号-4
打开技术之扣，分享程序人生！2610人阅读
算法设计与分析（5）
总的来说，可以用DFS（O（v^2））和BFS(O(v+e))的思想都能实现，只要从一个点出发，然后判断是否能遍历完所有的点。还有就是Tarjan算法和GABOW算法，这个没研究过，据说很好用。
实现办法一：用Warshall算法，时间复杂度为O（v^3），时间复杂度较大。
实现办法二：拓扑排序（多用于有向图）。
实现办法三：用BFS和visa[]标志数组，看看从一个点出发，是否能访问完所有的点。
实现办法四：用DFS，（思想和办法三相差无几，递归用while循环代替而已）核心代码如下：
&&&&&&&&&&&&&&&&&& 用邻接链表表示的图
&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&& void dfs(int s)
&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&& {
&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&& visit[s] =
&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&cnt++;
&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&& node* p = vnode[s];
&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&for (;p; p = p-&next)
&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&& {
&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&& if (!visit[p-&v])
&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&& dfs(p-&v);
&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&& }
&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&
&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&& }
&&&&&&&&&&&&&&& cnt为全局变量，当cnt与总结点数相等时，就连通。
下面把办法二和办法三用完全代码实现一下：
【无向图和邻接矩阵表示】
#include&iostream&
#include&queue&
#define MAX_VERTEX_NUM 20
typedef struct
}Adj,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
typedef struct
void CreateMGraph(MGraph &M)
&cout&&&请输入结点的个数:&;
&cout&&&请输入该图的邻接矩阵:&&&
&for(int i=1;i&=M.i++)
&&for(int j=1;j&=M.j++)
&&&cin&&M.arc[i][j].
void print(MGraph m)
&for(int i=1;i&=m.i++)
&&for(int j=1;j&=m.j++)
&&&cout&&m.arc[i][j].weight&&& &;
bool Connectivity_Warshall(MGraph m)
&judgemat.vexnum=m.
&for(i=1;i&=m.i++)
&&for(j=1;j&=m.j++)
&&&if(m.arc[i][j].weight)
&&&&judgemat.arc[i][j].weight=1; //初始化判断矩阵
&&&&judgemat.arc[i][j].weight=0;
&&judgemat.arc[i][i].weight=1;
&for(int x=1;x&=judgemat.x++) //采用warshall算法判断图的连通性。注意下标。
&&for(int y=1;y&=judgemat.y++)
&&&if(judgemat.arc[x][y].weight)
&&&&for(int z=1;z&=judgemat.z++)
&&&&&if(judgemat.arc[z][x].weight)
&&&&&&judgemat.arc[z][y].weight=1;
&&//print(judgemat);
&for(i=1;i&=judgemat.i++)
&&for(j=1;j&=judgemat.j++)
&&&if(!judgemat.arc[i][j].weight)//只要还没全为1就不连通。
/*用了广度优先搜索的思想*/
bool Connectivity_BFS(MGraph m)
&queue&int&
&bool visa[MAX_VERTEX_NUM];//之前先初始化为false
&int count=0;
&memset(visa,0,sizeof(visa));
&q.push(1);
&while(!q.empty())
&&int v=q.front();
&&visa[v]=
&&q.pop();
&&count++;
&&for(int i=1;i&=m.i++)//把与v连通并且没有被访问过的结点压进队列里面。
&&&if(m.arc[v][i].weight)
&&&&if(!visa[i])
&&&&&q.push(i);
&&&&&visa[i]=//标志被访问过。
&if(count==m.vexnum)//如果压进栈的结点个数刚好等于总结点的个数，则连通。
int main()
&MGraph MAP;
&CreateMGraph(MAP);
&cout&&&Use Warshall:&&&
&if(Connectivity_Warshall(MAP))
&&cout&&&Connectivity!&&&
&&cout&&&Not connectivity!&&&
&cout&&&Use BFS:&&&
&if(Connectivity_BFS(MAP))
&&cout&&&Connectivity!&&&
&&cout&&&Not Connectivity!&&&
&return 0;
* 以上用户言论只代表其个人观点，不代表CSDN网站的观点或立场
访问：178050次
积分：3151
积分：3151
排名：第6131名
原创：114篇
转载：22篇
评论：49条}