HDOJ 1232 通畅工程

HDOJ 1232 畅通工程

        因为我们三计算几何基本没接触，在看了两天的计算几何之后，伤心死了。还是图论的好啊，我喜欢图论。找了个简单的要死的题，看题目还是中文的，一看就只到求的是无向图的连通个数。因为点比较少，用矩阵存储就好了，直接DFS求连通。然后将不连通的图连一条路，ret(连通量)-1就是要修的最少的路了。

#include<stdio.h>
#include<string.h>
bool map[1000][1000],v[1000];
int n;
void DFS(int s)
{
     for(int i=1; i<=n; i++){
          if( map[s][i]&&!v[i]){
              v[i]=true;
              DFS(i);
          }
     }          
}
int main()
{
    int m,ret,i,j;
    while( scanf("%d",&n)&&n){
           memset(map,false,sizeof(map));
           memset(v,false,sizeof(v));
           scanf("%d",&m);
           ret=0;
           while( m--){
                  scanf("%d%d",&i,&j);
                  if(  !map[i][j]){
                       map[i][j]=true;
                       map[j][i]=true;
                  }
           }
           ret=0;
           for( i=1; i<=n; i++){
                if( !v[i]){
                    v[i]=true;
                    ret++;
                    DFS(i);
                }
           }
           printf("%d\n",ret-1);         
    }
    return 0;
}