连通图

Time Limit:1000MS  Memory Limit:65536K

Total Submit:17 Accepted:4

Description

 

Input

输入：每组数据的第一行是两个整数n 和m（0 < n <=100）。n 表示图的顶点

数目，0 < m <= 100 表示图中边的数目。如果n 为 0 表示输入结束。随后有m 行数据，每

行有两个值x 和y（0 < x , y <=n ），表示顶点x 和y 相连，顶点的编号从1 开始计

算。输入不保证这些边是否重复。

Output

输出：对于每组输入数据，如果所有从1~n所有顶点都是连通的，输出 ’YES’ ，否则输

出 ’NO’。

Sample Input

4 31 22 33 23 21 22 30 0

Sample Output

NOYES

#include

<

iostream

>

using

namespace

std;

int

n,m;

int

a,b;

int

i,j;

int

flag;

int

map[

101

][

101

];

int

used[

101

];

void

dfs(

int

x )

{

for

(

int

p

=

1

; p

<=

n; p

++

)

if

(map[x][p]

==

1

&&

used[p]

==

0

)

{

flag

++

;

used[p]

=

1

;

if

(flag

==

n

-

1

)

break

;

if

(p

<=

n

&&

flag

<

n

-

1

) dfs(p);

p

=

1

; //关键点

}

}

int

main()

{

while

(cin

>>

n

>>

m,n

+

m)

{

memset(map ,

0

,

sizeof

(map));

memset(used,

0

,

sizeof

(used));

for

(i

=

1

; i

<=

m; i

++

)

{

cin

>>

a

>>

b;

if

(a

!=

b) map[a][b]

=

map[b][a]

=

1

;

}

for

(i

=

1

; i

<=

n ; i

++

)

{

flag

=

0

;

for

(j

=

1

; j

<=

n; j

++

)

{

memset(used,

0

,

sizeof

(used));

if

(map[i][j]

==

1

&&

i

!=

j )

{

flag

=

0

;

used[i]

=

1

; used[j]

=

1

;

flag

++

;

dfs(j);

if

(flag

==

n

-

1

)

break

;

}

}

if

(flag

==

n

-

1

)

break

;

}

if

(flag

==

n

-

1

) cout

<<

"

YES

"

<<

endl;

else

cout

<<

"

NO

"

<<

endl;

}

return

0

;

}