圖的應用之--圖的連通

題目描述

給定一個圖的鄰接矩陣，請判斷該圖是否是連通圖。連通圖：任意兩個頂點之間都有路徑。

輸入

第1行輸入一個整數k，表示有k個測試資料 第2行輸入一個整數n，表示有n個結點 從第3行起到第n+2行輸入一個鄰接矩陣，其中Matrix[i,j]=1表示第i，j個結點之間有邊，否則不存在邊。 接下來是第2到第k個測試資料的結點數和鄰接矩陣

輸出

輸出Yes or No表示圖是否是強連通圖

樣例輸入

2 4 0 1 1 1 1 0 1 1 1 1 0 1 1 1 1 0 7 0 1 0 0 0 0 0 0 0 1 1 0 0 0 1 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 1 1 0 1 0 0 0 0 0 0 0 0 1 0 1 0

樣例輸出

Yes No   這道題隻需對每一個頂點調用一次深度周遊，設定一個count，對于每個頂點，周遊前count=0，判斷周遊後count==vexnum ？ 若對于每一個頂點都有count==vexnum就說明這個圖是強連通的

#include<iostream>
using namespace std;
const int MaxLen = 20;
class Map
{
private:
    bool Visit[MaxLen];
    int Matrix[MaxLen][MaxLen];
    int Vexnum;
    void DFS(int v)
    {
        int w, i, k;
        Visit[v] = true;
        count1++;
        //cout<<v<<" ";
        //尋找鄰接點
        int *AdjVex = new int[Vexnum];
        for (i = 0; i < Vexnum; i++)
            AdjVex[i] = -1;
        k = 0;
        for (i = 0; i < MaxLen; i++)
            if (Matrix[v][i] == 1)
                AdjVex[k++] = i;
        i = 0;
        for (w = AdjVex[i++]; w >= 0; w = AdjVex[i++])
        {
            if (Visit[w] == false)
                DFS(w);
        }
        delete[]AdjVex;
    }
public:
    int count1;
    void SetMatrix(int vnum, int mx[MaxLen][MaxLen])
    {
        int i, j;
        Vexnum = vnum;
        for (i = 0; i < MaxLen; i++)
            for (j = 0; j < MaxLen; j++)
                Matrix[i][j] = 0;
        for (i = 0; i < Vexnum; i++)
            for (j = 0; j < Vexnum; j++)
                Matrix[i][j] = mx[i][j];
    }
    void DFSTraverse()
    {
        int v, i;
        for (i = 0; i < Vexnum; i++)
            Visit[i] = false;
        for (v = 0; v < Vexnum; v++)
            if (!Visit[v])
                DFS(v);
        cout << endl;
    }
    int lt()
    {
        int i, j;
        for (i = 0; i < Vexnum; i++)
        {
            for (j = 0; j < Vexnum; j++)
                Visit[j] = false;
            count1 = 0;
            DFS(i);
            if (count1 != Vexnum)
                return 0;
        }
        return 1;
    }
};
int main()
{
    int t;
    cin >> t;
    while (t--)
    {
        int n, i, j;
        cin >> n;
        int a[MaxLen][MaxLen];
        for (i = 0; i < n; i++)
            for (j = 0; j < n; j++)
                cin >> a[i][j];
        Map map;
        map.SetMatrix(n, a);
        if (map.lt())
            cout << "Yes" << endl;
        else
            cout << "No" << endl;
    }
}      

轉載于:https://www.cnblogs.com/Liu269393/p/10223580.html