Connected Graph

Time Limit:

2000MS

Memory Limit:

65536K

Description

一个无向图G，给定N个顶点，其中一些顶点之间有边相连。希望知道图G是否为连通图。

Input

首先，第一行输入整数N和E。 N表示顶点个数（1≤N≤100）, 顶点标号为1，2，…，N。E表示边数（1≤E≤5000）。

接下来有E行，每行有两个顶点标号u和v，表明u和v是相邻关系。

Output

如果图G是连通图，输出YES，否则，输出NO。

Sample Input

9 10

2 4

5 7

1 3

8 9

1 2

5 6

2 3

7 9

6 8

6 9

Sample Output

Hint

No hint.

Source

解题代码：

 1 #include<iostream>
 2 using namespace std;
 3 int find(int *&A,int a,int b)
 4 {
 5     if(A[a]==A[b])
 6         if(A[a]==-1)
 7             return 0;
 8         else
 9             return 1;
10     else
11         return 2;
12 }
13 
14 void unite(int *&A,int a,int b,int n,int &t,int k)
15 {
16     if(k==0)
17     {
18         A[a]=t;
19         A[b]=t++;
20     }
21     else if(k==2)
22     {
23         if(A[a]==-1)
24             A[a]=A[b];
25         else if(A[b]=-1)
26             A[b]=A[a];
27         else
28         {
29             int f=A[b];
30             for(int i=0;i<n;i++)
31             {
32                 if(A[i]==f)
33                     A[i]=A[a];
34             }
35         }            
36     }
37 }
38 
39 int main()
40 {
41     int n,e;
42     int a,b;
43     int t=1;
44     cin>>n>>e;
45     int *A=new int[++n];
46     for(int i=0;i<n;i++)
47         A[i]=-1;
48     while(e-->0)
49     {
50         cin>>a>>b;
51         unite(A,a,b,n,t,find(A,a,b));
52     }
53     if(A[1]==-1)
54     {cout<<"NO\n";
55     return 0;
56     }
57     for(int i=2;i<n;i++)
58     {
59         if(A[i]!=A[1])
60         {
61             cout<<"NO\n";
62             return 0;
63         }
64     }
65     cout<<"YES\n";
66 }

优质内容筛选与推荐>>
1、面向对象之: 类空间问题及类之间的关系
2、 ECO传奇（II）
3、Manthan, Codefest 16 D. Fibonacci-ish 暴力
4、四则运算
5、Linux 内核 NuBus 总线

0 │ 收藏 │ 举报