題目描述：

給定一個無向圖和其中的所有邊，判斷這個圖是否所有頂點都是連通的。

輸入：

每組數(shù)據(jù)的第一行是兩個整數(shù) n 和 m（0<=n<=1000）。n 表示圖的頂點數(shù)目，m 表示圖中邊的數(shù)目。如果 n 為 0 表示輸入結束。隨后有 m 行數(shù)據(jù)，每行有兩個值 x 和 y（0<x, y <=n），表示頂點 x 和 y 相連，頂點的編號從 1 開始計算。輸入不保證這些邊是否重復。

輸出：

對于每組輸入數(shù)據(jù)，如果所有頂點都是連通的，輸出"YES"，否則輸出"NO"。

樣例輸入：

4 3
1 2
2 3
3 2
3 2
1 2
2 3
0 0

樣例輸出：

NO
YES

#include<iostream>
#include<stdio.h>
#include<string.h>
using namespace std;

int a[1001][1001];
int visit[1001];
int n, m;

void DFS(int i)
{
    int j;
    visit[i] = 1;
    for(int j = 2; j <= n; j++)
    {
	if( a[i][j] == 1 && visit[j] == 0)
	    DFS(j);
    }
}

int main()
{
    freopen("a.in","r", stdin);
    while( cin >> n >> m)
    {
	int A, B;
	bool flag;
	if( n == 0 && m == 0)
	    break;
	memset(visit, 0, sizeof(visit));
	memset(a, 0, sizeof(a));
	for( int i = 0; i < m; i++)
	{
	    cin >> A >> B;
	    a[A][B] = 1;
	    a[B][A] = 1;
	}
	DFS(1);
	flag = true;
	for(int i = 1; i <= n; i++)
	    if(visit[i] == 0)
		flag = false;
	if(flag)
	    cout << "YES" << endl;
	else
	    cout << "NO" << endl;

    }
    return 0;
}

　　

給夢想一點時間

總結

以上是生活随笔為你收集整理的【慢慢学算法】：连通图的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。