(一)九度上一個練習題
- 題目描述:
- 給定一個無向圖和其中的所有邊,判斷這個圖是否所有頂點都是連通的。
- 輸入:
- 每組資料的第一行是兩個整數 n 和 m(0<=n<=1000)。n 表示圖的頂點數目,m 表示圖中邊的數目。如果 n 為 0 表示輸入結束。随後有 m 行資料,每行有兩個值 x 和 y(0<x, y <=n),表示頂點 x 和 y 相連,頂點的編号從 1 開始計算。輸入不保證這些邊是否重複。
- 輸出:
- 對于每組輸入資料,如果所有頂點都是連通的,輸出"YES",否則輸出"NO"。
- 樣例輸入:
-
4 3 1 2 2 3 3 2 3 2 1 2 2 3 0 0
- 樣例輸出:
-
NO YES
(二)判斷圖是否是連通的,可以通過深度優先周遊的方法判斷。具體實作為:在圖中標明任一一個頂點,對該頂點進行深度優先周遊,如果在這個周遊過程中所有的頂點都被周遊到,則該圖為連通;反之,若存在沒有被周遊到的頂點,則說明該圖是非連通的。實作代碼如下(針對無向圖,使用鄰接表結構):
#include <iostream>
#include <string.h>
using namespace std;
#define MAX_NODE 1000
typedef struct ArcNode
{
int adjvex;//弧指向的節點的值(點的标号)
ArcNode* next;//指向下一條弧
ArcNode(int value)
{
adjvex = value;
next = NULL;
}
};//鄰接表節點
typedef struct
{
int vexdata; //頭節點的标号
struct ArcNode* firstarc;//第一個鄰接表節點的位址
}VexNode, AdjList[MAX_NODE];//頭結點
typedef struct
{
AdjList vexNodes;
int vexNum;
int arcNum;//目前節點數目和弧數
}GraphWithAL;//鄰接表表示的圖
//檢測要輸入的邊是否已經存在,針對無向圖
bool CheckArcIsExist(GraphWithAL* G, int v1, int v2)
{
ArcNode* temp = G->vexNodes[v1-1].firstarc;
while(temp!=NULL)
{
if(temp->adjvex == v2)
return true;
temp = temp->next;
}
return false;
}
//建立圖,vexNum代表頂點的個數,arcNum代表邊的個數,isUnDirected代表的是 是否是無向圖
void CreateGraph(GraphWithAL* G, int vexNum, int arcNum, bool isUnDirected)
{
memset(G, 0 ,sizeof(GraphWithAL));
//初始化頭結點
int i = 0;
for(i=0; i<vexNum; ++i)
{
G->vexNum = vexNum;
G->vexNodes[i].firstarc = NULL;
G->vexNodes[i].vexdata = i+1;//從1開始計算頂點
}
//初始化邊
for(i=0; i<arcNum; ++i)
{
//輸入邊的頂點和尾點
int v1, v2;
cin>>v1>>v2;
if(CheckArcIsExist(G, v1, v2))
continue;
ArcNode* arcNode = new ArcNode(v2);
//還需要檢驗邊是否已經存在,這裡沒有檢驗
arcNode->next = G->vexNodes[v1-1].firstarc;
G->vexNodes[v1-1].firstarc = arcNode;
G->arcNum++;
if(isUnDirected)
{
ArcNode* arcNode = new ArcNode(v1);
//還需要檢驗邊是否已經存在,這裡沒有檢驗
arcNode->next = G->vexNodes[v2-1].firstarc;
G->vexNodes[v2-1].firstarc = arcNode;
}
}
}
//對第vex個頂點遞歸的做深度優先周遊, 若周遊到該頂點則将visit數組中對應的值置為true
void DFS(GraphWithAL* G, int vex, bool* visit)
{
//cout<<vex<<endl;
visit[vex-1] = true;
ArcNode* temp = G->vexNodes[vex-1].firstarc;
if(temp == NULL)
{
//cout<<vex<<"->null"<<endl;
return ;
}
while(temp != NULL)
{
if(!visit[temp->adjvex-1])
{
//cout<<vex<<"->"<<temp->adjvex<<endl;
visit[temp->adjvex-1] = true;
DFS(G, temp->adjvex, visit);
}
temp = temp->next;
}
}
//深度優先周遊 圖
void DFS_Visit(GraphWithAL* G)
{
bool* visit = new bool[G->vexNum];
memset(visit, 0, G->vexNum);
int i=0;
for(i=0; i<G->vexNum; ++i)
{
if(!visit[i])
DFS(G, i+1, visit);
}
}
//檢測圖是否是連通的
bool CheckGraphIsConnected(GraphWithAL* G)
{
bool* visit = new bool[G->vexNum];
memset(visit, 0, G->vexNum);
DFS(G, 1, visit);
int i=0;
for(i=0; i<G.vexNum; ++i)
{
if(!visit[i])
return true;
}
return false;
}
int main()
{
GraphWithAL G;
int n, m;
while(cin>>n>>m)
{
if(n==0)
break;
CreateGraph(&G, n, m, true);
//DFS_Visit(&G);
//檢測圖是否連通
bool flag = CheckGraphIsConnected(&G);
if(flag)
cout<<"NO"<<endl;
else
cout<<"YES"<<endl;
}
return 0;
}