这道题跟HDU 1213 How Many Tables 并查集很接近，都是赤裸裸的并查集的题。

思路：如果还须要建n-1条路。每并一次就自减1。

參考代码：

#include<stdio.h>

int fa[1000];

int find(int u)

{

    return fa[u]==u?

u:fa[u]=find(fa[u]);

}

int main()

{

    int i,n,m,u,v,x,y;

    scanf("%d%d",&n,&m);

    while (n)

    {

        for (i=1;i<=n;i++) fa[i]=i;

        for (i=1;i<=m;i++)

        {

            scanf("%d%d",&u,&v);

            x=find(u);y=find(v);

            if (x!=y)

            {

                fa[x]=y;

                n--;

            }

        }

        n--;

        printf("%d\n",n);

       scanf("%d%d",&n,&m);

    }

   return 0;

}

优化：先用数组储存m组数，然后仅仅对这些节点的根节点

赋初值fa[u[i]]=u[i];fa[v[i]]=v[i];

參考代码：

#include<stdio.h>

int fa[1000],u[1000],v[1000];

int find(int u)

{

    return fa[u]==u?u:fa[u]=find(fa[u]);

}

int main()

{

    int i,n,m,x,y;

    scanf("%d%d",&n,&m);

    while (n)

    {

        for (i=1;i<=m;i++)

        {

            scanf("%d%d",&u[i],&v[i]);

            fa[u[i]]=u[i];

            fa[v[i]]=v[i];

        }

        for (i=1;i<=m;i++)

        {

          x=find(u[i]);y=find(v[i]);

            if (x!=y)

            {

                fa[x]=y;

                n--;

            }

        }

        n--;

        printf("%d\n",n);

       scanf("%d%d",&n,&m);

    }

   return 0;

}