图的连通性问题

作者:czp 分类: PAT 发布于:2016-12-28 14:28 ė956次浏览 60条评论
Time limit: 1000MS    Memory limit: 32768K 
Total Submit: 12    Accepted: 7 

【问题描述】

图论中有一个基本的问题,那就是一个无向图的连通性判别问题,今天我们就来讨论这个问题,我们知道,在计算机中一张图可以有两种表示方法,一是邻接矩阵二是邻接表,其中的邻接矩阵表示方法,我们已经在课堂上介绍最小生成树问题时讨论过,今天我们就来讨论用邻接表表示的图的连通性问题。

【输入说明】

本问题有多组测试数据,每组测试数据有两部分,第一部分只有一行,是两个正整数,分别表示图的节点数N(节点编号从1N1<=N<=100)和图的边数E;第二部分共有E行,每行也是两个整数N1N21<=N1N2<=N),分别表示N1N2之间有一条边。

【输出说明】

对于每一组测试数据,输出只有一行,如果是连通图,那么输出“Yes”,否则输出“No”。

Sample Input

6 10

1 2

1 3

1 4

1 5

1 6

2 3

2 4

3 4

3 5

3 6

4 3

1 2

1 3

2 3

 

Sample Output

Yes

No


#include<iostream>

using namespace std;

int main() {
    int n, e;
    int n1, n2;
    int i;
    int temp;

    while (cin >> n >> e) {
        int group[101];
        for (i = 1; i <= n; i++) {
            group[i] = i;
        }

        while (e--) {
            cin >> n1 >> n2;
            if (group[n1] != group[n2]) {
                temp = group[n2];
                for (i = 1; i <= n; i++) {
                    if (group[i] == temp) {
                        group[i] = group[n1];
                    }
                }
            }
        }

        for (i = 2; i <= n; i++) {
            if (group[i] != group[i - 1]) {
                break;
            }
        }

        cout << (i > n ? "Yes" : "No") << endl;
    }

    return 0;
}

本文出自 czp的装逼站,转载时请注明出处及相应链接。

0

发表评论

电子邮件地址不会被公开。必填项已用*标注


Ɣ回顶部