判斷一個無向圖是否為連通圖的方法
無向圖的連通性
判斷一個無向圖是否為連通圖。輸入為無向圖的鄰接矩陣。
輸入
- 輸入有若干行
- 第一行為正整數(shù)N(0<N<=3000),代表圖中點(diǎn)的個數(shù)
- 接下來N行,每行有N個數(shù)據(jù),每個數(shù)據(jù)以空格分隔,代表鄰接矩陣。
輸出
- 一行。連通yes, 否則no.
測試輸入
3
1 1 1
1 1 1
1 1 1
測試輸出
yes
源代碼
#include<stdio.h> #define N 3002 int a[N][N]; int main() { int i,j,k,n; scanf("%d\n",&n); for(i=0;i<n;i++) for(j=0;j<n;j++) scanf("%d",&a[i][j]); for(k=0;k<n;k++) for(i=0;i<n;i++) if(a[k][i]) for(j=0;j<n;j++) if(a[i][k]&&a[k][j]){ a[i][j]=1; } for(i=0;i<n;i++) for(j=0;j<n;j++) { if(a[i][j]+a[j][i]==0){ printf("no\n");return 0;} } printf("yes\n"); }
總結(jié)
以上就是這篇文章的全部內(nèi)容了,希望本文的內(nèi)容對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值,謝謝大家對腳本之家的支持。如果你想了解更多相關(guān)內(nèi)容請查看下面相關(guān)鏈接
- C++面試基礎(chǔ)之static關(guān)鍵字詳解
- C++稀疏矩陣的各種基本運(yùn)算并實(shí)現(xiàn)加法乘法
- Dijkstra算法最短路徑的C++實(shí)現(xiàn)與輸出路徑
- C++項(xiàng)目求Fibonacci數(shù)列的參考解答
- C++實(shí)踐IP地址類項(xiàng)目參考
- C++實(shí)踐數(shù)組作數(shù)據(jù)成員的參考
- 一張圖總結(jié)C++中關(guān)于指針的那些事
- C++實(shí)踐數(shù)組類運(yùn)算的實(shí)現(xiàn)參考
- C++實(shí)踐Time類中的運(yùn)算符重載參考方法
- C++實(shí)踐分?jǐn)?shù)類中運(yùn)算符重載的方法參考
相關(guān)文章
C++?STL容器詳解之紅黑樹部分模擬實(shí)現(xiàn)
本文主要對紅黑樹進(jìn)行了詳細(xì)介紹,并對其核心功能進(jìn)行了模擬實(shí)現(xiàn)。文中的代碼對我們的學(xué)習(xí)或工作有一定的價值,感興趣的小伙伴可以了解一下2021-12-12C語言科學(xué)計算入門之矩陣乘法的相關(guān)計算
這篇文章主要介紹了C語言科學(xué)計算入門之矩陣乘法的相關(guān)計算,文章中還介紹了矩陣相關(guān)的斯特拉森算法的實(shí)現(xiàn),需要的朋友可以參考下2015-12-12VisualStudio2022配置opencv的實(shí)現(xiàn)
本文主要介紹了VisualStudio2022配置opencv的實(shí)現(xiàn),文中通過圖文介紹的非常詳細(xì),對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值,需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2024-06-06QT開發(fā)應(yīng)用程序的歡迎界面實(shí)例
下面小編就為大家?guī)硪黄猀T開發(fā)應(yīng)用程序的歡迎界面實(shí)例。小編覺得挺不錯的,現(xiàn)在就分享給大家,也給大家做個參考。一起跟隨小編過來看看吧2017-08-08Dev C++編譯時運(yùn)行報錯source file not compile問題
這篇文章主要介紹了Dev C++編譯時運(yùn)行報錯source file not compile問題,具有很好的參考價值,希望對大家有所幫助,如有錯誤或未考慮完全的地方,望不吝賜教2024-01-01C++實(shí)現(xiàn)LeetCode(206.倒置鏈表)
這篇文章主要介紹了C++實(shí)現(xiàn)LeetCode(206.倒置鏈表),本篇文章通過簡要的案例,講解了該項(xiàng)技術(shù)的了解與使用,以下就是詳細(xì)內(nèi)容,需要的朋友可以參考下2021-07-07