HDOJ1232 ( 畅通工程 ) 【并查集】

Code Render Status : Rendered By HDOJ C Code Render Version 0.01 Beta

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

<code>#include &lt;stdio.h&gt;</code>

<code>#include &lt;string.h&gt;</code>

<code>int</code> <code>set[1005],s,n;</code>

<code>void</code> <code>MergeSet(</code><code>int</code> <code>a,</code><code>int</code> <code>b)</code>

<code>{</code>

<code>    </code><code>int</code> <code>i;</code>

<code>    </code><code>s--;</code>

<code>    </code><code>for</code> <code>(i=0;i&lt;n;i++)</code>

<code>    </code><code>{</code>

<code>        </code><code>if</code><code>(set[i]==a)</code>

<code>            </code><code>set[i]=b;</code>

<code>    </code><code>}</code>

<code>}</code>

<code>int</code> <code>main()</code>

<code>    </code><code>int</code> <code>i,m,a,b,f,t;</code>

<code>    </code><code>while</code><code>(</code><code>scanf</code><code>(</code><code>"%d"</code><code>,&amp;n),n)</code>

<code>        </code><code>s=n-1;</code>

<code>        </code><code>scanf</code><code>(</code><code>"%d"</code><code>,&amp;m);</code>

<code>        </code><code>for</code> <code>(i=0;i&lt;n;i++)</code>

<code>            </code><code>set[i]=i;</code>

<code>        </code><code>for</code> <code>(i=0;i&lt;m;i++)</code>

<code>        </code><code>{</code>

<code>            </code><code>scanf</code><code>(</code><code>"%d%d"</code><code>,&amp;a,&amp;b);</code>

<code>            </code><code>f=set[a-1];</code>

<code>            </code><code>t=set[b-1];</code>

<code>            </code><code>if</code><code>(f!=t)</code>

<code>                </code><code>MergeSet(f,t);</code>

<code>        </code><code>}</code>

<code>        </code><code>printf</code><code>(</code><code>"%d\n"</code><code>,s);</code>

<code>    </code><code>return</code> <code>0;</code>

本文转自ZH奶酪博客园博客，原文链接：http://www.cnblogs.com/CheeseZH/archive/2012/05/13/2498073.html，如需转载请自行联系原作者