lzh

刘政
posts - 17, comments - 1, trackbacks - 0, articles - 1

置顶随笔

/*刚拿此题时一头雾水,当看完一次同余方程时方才有点头绪.....后来在又在求最值问题上遇到麻烦。最后才在数学推导下才AC此题.....第一次深刻体会到数学对解题的重要性....下面说一下我的解题思路.....
1.首先通过Gcd函数求出n1,n2的最大公约数g以及满足条件的x,y:  n1*x+n2*y=n;(递归运用:x0=1,y0=0;x=y1,y=(x1-n1/n2*y1))
显然当n不能被g整除时显然没解....这里有一个问题:Gcd函数求出的x,y为什么刚好能使得|x|+|y|最小??请求数学达人指导
2.求出满足条件的m1,m2使得m1*n1+m2*n2=n  (1):由1得,x*n1+y*n2=g (2)....结合(1(2):m1=n*x/g+t*n2/g,m2=n*y/g-t*n1/g;这里的t是一个参数,但仍能满足(1)式。
3.由m1>=0,m2>=0可得他t1=<t<=t2;(注意t的取值必须为整数)
4.由c=c1*m1+c2*m==》c=num1+t*(c1*n2-c2*n1)....因此c的大小取决于c1*n2-c2*n1的正负以及t的值....之后的过程在代码中很明了了。
 1 #include<iostream>
 2 #include<math.h>
 3 using namespace std;
 4 long Gcd(long p,long q,long *x,long *y)
 5 {
 6     long x1,y1;
 7     long g;
 8     if(q>p)
 9         return (Gcd(q,p,y,x));
10     if(q==0)
11     {
12         *x=1;
13         *y=0;
14         return p;
15     }
16     g=Gcd(q,p%q,&x1,&y1);
17     *x=y1;
18     *y=(x1-p/q*y1);
19     return g;
20 }
21 int main()
22 {
23
24     long n,c1,c2,n1,n2,x,y,gcd,t1,t2,t,a,b;
25     //freopen("c:\\in.txt","r",stdin);
26 //    freopen("c:\\8522.out","w",stdout);
27     while(cin>>n)
28     {
29         if(n==0)
30             break;
31         cin>>c1>>n1>>c2>>n2;
32         gcd=Gcd(n1,n2,&x,&y);
33         t1=ceil(-n*(double)x/(double)n2);
34         t2=floor(n*(double)y/(double)n1);
35         if((t1>t2)||(n%gcd!=0))
36         {
37             cout<<"failed\n";
38             continue;
39         }
40         if(c1*n2>=c2*n1)
41             t=t1;
42         
43         else
44           t=t2;
45         a=n*x/gcd+t*n2/gcd;
46         b=n*y/gcd-t*n1/gcd;
47         cout<<a<<" "<<b<<endl;
48     }
49     return 0;
50 }

posted @ 2010-08-22 11:18 lzh525 阅读(406) | 评论 (0)编辑 收藏

     摘要: 全排列的生成1 #include<iostream> 2 using namespace std; 3 4 const int MAX=100; 5 int a[MAX]; 6 bool finished=false;//是否找到了所要全部求的解 7 8 void process(int *a,int n) 9 { 10 int i,fir...  阅读全文

posted @ 2010-08-22 10:58 lzh525 阅读(833) | 评论 (0)编辑 收藏

2011年4月25日

#include using namespace std; int gcd(int x,int y) {//欧几里得:辗转相除法 if(x>1,y>>1) //若x偶,y奇, 则f(x,y)=f(x>>1,y) //若x奇,y偶, 则f(x,y)=f(x,y>>1) //若x,y都为奇数,f(x,y)=f(y,x-y),那么在f(x,y)=f(y,x-y)之后(x-y)是一个偶数,下一步会有除以2的操作,所以最坏情况下的时间复杂度O(log2(max(x,y))) int f2(int x,int y) { if(x>1,y>>1)<<1); else return f2(x>>1,y); } else { if(y%2==0) return f2(x,y>>2); else return f2(y,x-y); } } } int main() { int m,n; while(cin>>m>>n) { printf("%d与%d的最大公约数为:\n",m,n); //cout<

posted @ 2011-04-25 22:34 lzh525 阅读(283) | 评论 (0)编辑 收藏

2011年4月3日

Tempter of the Bone Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 21915 Accepted Submission(s): 6011 Problem Description The doggie found a bone in an ancient maze, which fascinated him a lot. However, when he picked it up, the maze began to shake, and the doggie could feel the ground sinking. He realized that the bone was a trap, and he tried desperately to get out of this maze. The maze was a rectangle with sizes N by M. There was a door in the maze. At the beginning, the door was closed and it would open at the T-th second for a short period of time (less than 1 second). Therefore the doggie had to arrive at the door on exactly the T-th second. In every second, he could move one block to one of the upper, lower, left and right neighboring blocks. Once he entered a block, the ground of this block would start to sink and disappear in the next second. He could not stay at one block for more than one second, nor could he move into a visited block. Can the poor doggie survive? Please help him. Input The input consists of multiple test cases. The first line of each test case contains three integers N, M, and T (1 < N, M < 7; 0 < T < 50), which denote the sizes of the maze and the time at which the door will open, respectively. The next N lines give the maze layout, with each line containing M characters. A character is one of the following: 'X': a block of wall, which the doggie cannot enter; 'S': the start point of the doggie; 'D': the Door; or '.': an empty block. The input is terminated with three 0's. This test case is not to be processed. Output For each test case, print in one line "YES" if the doggie can survive, or "NO" otherwise. Sample Input 4 4 5 S.X. ..X. ..XD .... 3 4 5 S.X. ..X. ...D 0 0 0 Sample Output NO YES /*刚看到提示觉得就是一个普通的棋盘搜索的问题,因为以前做过所以马上开始敲代码,到后来发现连测试数据都过不了,再后来就是WA。后面记过调试才发现循环搜索遍历后没复原。后来终于自己的测试数据都过了,提交后才悲剧地发现TLE。看了很久之后觉得到网上找答案了,原来是一个剪枝没处理 。铜鼓这个题又又发现了很多问题 1.基本的算法要熟悉弄通,例如此题就是一个典型的DFS,我很久前学过但没怎么用,没很好的掌握。开始做时完全按照自己的思路,虽然写出来了但效率不高 2.算法效率越见重要,最后还是一个数学问题,多总结 */ //下面是自己盲目写的算法,虽然册数数据过了但超时 /*#include #include using namespace std; #define N 8 char maze[N][N]; bool flag[N][N]; int direction[4][2]={0,1,1,0,0,-1,-1,0}; bool sign; int num; void init() { int i,j; for(i=0;i=s) { if(maze[x][y]=='D') { sign=true; return ; } else continue; } else { if(maze[x][y]=='D') continue; else { cout<>row>>column>>limit) { getchar(); // if(!(row|column|limit)) //全0则输入结束 // break; if(0==row&&0==column&&0==limit) return 0; init(); for(i=1;i<=row;i++) { for(j=1;j<=column;j++) { cin>>maze[i][j]; if(maze[i][j]=='S') { Ss=i; Se=j; } if(maze[i][j]!='X') { flag[i][j]=true; num++; } } getchar(); } times=0; num=0; sign=false; flag[Ss][Se]=false; if(num-1>=limit) //限制的时间小于等于所有的街区数时才有可能有解 search(Ss,Se,limit,times); if(sign) cout<<"YES\n"; else cout<<"NO\n"; } return 0; } */ //之后经过剪枝后的代码 AC #include #include using namespace std; #define N 8 int ex,ey; //出口位置 int secs; //出口开启时间 bool sign; //找到出口的标志 bool flag[N][N]; //是否遍历过的标记数组 char maze[N][N]; int direction[4][2]={0,1,1,0,0,-1,-1,0}; void init() { int i,j; for(i=0;i>row>>column>>secs) { getchar(); //吸收回车 if(!(row|column|secs)) //全0则输入结束 break; init(); nums=0; sign=false; for(i=1;i<=row;i++) { for(j=1;j<=column;j++) { cin>>maze[i][j]; if(maze[i][j]=='S') { x0=i; y0=j; } else if(maze[i][j]=='D') { ex=i; ey=j; flag[i][j]=true; } else if(maze[i][j]=='X') nums++; else flag[i][j]=true; } getchar(); //吸收回车 } if(row*column-nums-1>=secs) dfs(x0,y0,0); if(sign) cout<<"YES\n"; else cout<<"NO\n"; } return 0; }

posted @ 2011-04-03 21:37 lzh525 阅读(599) | 评论 (0)编辑 收藏

2010年11月12日

KMP算法是一种高效的模式匹配算法,复杂度可以达到O(m+n),而普通模式匹配算法的复杂度为O(m*n)。

普通模式匹配算法

  从主串的第一个字符(或者给定的第pos个字符)开始和子串的第一个字符开始比较,若相等,则继续比较后面的字符。若不相等,则从主串本次开始比较的字符的下一个字符开始,与子串的第一个字符进行比较(即主串需要回退到本次比较开始字符的下一字符,模式串回退到首字符,主串与子串都需要回退)。
  匹配成功的标志:比较到子串的’\0’
  匹配失败的标志:比较到主串的’\0’,且此时子串的比较位不等于’\0’。
  算法复杂度:O(m*n)

KMP算法

KMP算法的改进思路
  在普通匹配算法中子串与模式串都需要回溯,但这些回溯不是必要的。因为当某一位发生失配时,可以根据已匹配的结果进行判断。该算法问题可以理解为,当模式串中的第k位与主串的第i位比较时发生不匹配时,需要将模式串向右滑动到哪里继续与主串的第i位进行比较?避免了不必要的主串回溯,减少了模式串回溯的位数,从而使算法复杂度提升到O(m+n)。

KMP算法的实现思路
  从主串的第一个字符(或者给定的第pos个字符)开始和子串的第一个字符开始比较,若相等,则继续比较后面的字符。若不相等,则将模式串右移至合适的位置,找出模式串中合适的第k位与主串中发生不等的位进行对齐比较。算法继续。
  模式串与主串对齐继续比较的第k位必须满足其前k-1位与主串发生失配位置的前k-1位匹配,且该k-1位字串必须是最长的字串(即不存在k’>k,使模式串中的前k’-1位与主串发生失配位置的前k’-1位匹配,这是为了保证不漏过可以匹配的串)。
  该算法中的主程序同普通的匹配算法类似,区别在于当发生不匹配时,主串指针不需要回退(不动),将模式串右移到合适的位置继续进行比较。当模式串移动到第一位(下标为0)仍然不等时,主串指针右移一位。该算法的关键是模式串next[]的取得。
  匹配成功的标志:比较到子串的’\0’
  匹配失败的标志:比较到主串的’\0’,且此时子串的比较位不等于’\0’。

next[]数组的获得
  next[]数组记录了当模式串第j位发生失配时,模式串需要移动到第k位,使第k位与主串发生失配的位对齐继续比较(next[j]=k)。next[]数组使用递推实现,假设next[j]=k已经获得,则从next[j]开始推next[j+1]。具体算法如下。
  假设next[j]=k(第j位及之前的next[]值已经求得,k<j),当模式串第j位发生失配时,模式串需要移动到第k位,使第k位与主串发生失配的位对齐继续比较。这说明:除了第k位,其前面的k-1位与主串发生失培的前k-1位已经匹配。(因为当第p[k]位失配时,p[1]p[2]…p[k-1]已经等于s[i-k+1]s[i-k+2]…s[i-1])
  而同时由于:p[j-k+1]p[j-k+2]…p[j-1]=s[i-k+1]s[i-k+2]…s[i-1]
  所以:p[1]p[2]…p[k-1]= p[j-k+1]p[j-k+2]…p[j-1]

情况1:
  若p[k]=p[j],即p[next[j]]=p[j],那么:p[1]p[2]…p[k-1]p[k]= p[j-k+1]p[j-k+2]…p[j-1]p[j],则根据定义:next[j+1]=k+1=next[j]+1

情况2:
  若p[k]!=p[j],即p[1]p[2]…p[k-1]p[k]!= p[j-k+1]p[j-k+2]…p[j-1]p[j],即p[k]与p[j]发生不等。把p[k]为模式串,即模式串第k位发生失配,根据KMP算法的基本思路,当模式串第k位发生失配时,模式串应移动到第next[k]=k’位与主串进行比较。此时:p[1]p[2]…p[k’-1]= p[j-k’+1]p[j-k’+2]…p[j-1]。然后再比较p[k’]与p[j],若相等,同情况1:next[j+1]=k’+1= next[k]+1;若不相等,返回到情况2的头进行比较。(两种判断均可以归入情况1或者情况2,所以可以进行循环)

情况3:
  若next[k]=-1,即发生失配元素的前一个元素与第一个元素a[0]仍然不等,该应使该失配元素直接与第一个元素比较,next[j+1]=0。(该情况可与第一种情况合并(因为next[0]=-1))

简单得说:
  从next[j]=k开始比较,首先将k与自身对齐比较(找可以与j对齐比较的最长子串),如果相等,则p[k]=p[j],满足情况1。若不相同,即模式串第k位发生失配,移动到k'=next[k]位继续进行比较。返回情况1或者2。如果next[k]=-1(仅第1位的next[0]的值为-1),说明j+1的前一位j与第一位比较仍然不等,那应该让第j+1位直接与第1位(下标为0)进行比较。
  next[k+1]的计算依赖于next[k],next[k+1]仅有一种方式获得,即第k+1字符的前面k个字符完全匹配(或者前一元素与第一个元素仍然不匹配)。而next[k]是已经计算的,即next[k]可以保证第k字符的前面k-1个字符(除了第k个字符)完全匹配,而且该字串是最长字串。因为只需比较第k个字符是否匹配。匹配成功即情况一,匹配失败则继续寻找next[next[k]]。
  编程时,每次进行计算next[j+1]时,必须保证j与k呈对应关系,即每新一次计算前,next[j]=k(next[j+1]=k+1,因而也可以写成next[++j]=++k)。

KMP算法的再改进

  当第k+1位发生失配时,根据原算法,可以找到一个子串,与之匹配。此时,next[j+1]=k+1
但若 T[j+1]= T[next[j+1]]=T[k+1],则当T[j+1]发生失配时,程序会使回到第next[j+1](=k+1)位,与T[j+1]所对应的主串字符进行比较。但由于主串字符已经不等于T[j+1],因而也必然不等于T[next[j+1]],因而此次比较必然失败。
  改进:当T[j+1]= T[next[j+1]]=T[k+1]时,next[j+1]= next[next[j+1]]=next[k+1],从而避免不必要的重复比较。

附:
普通模式匹配算法代码:
int mystrstr(char* S, char* T, int pos)
{
    int i=pos; //设置主串的指针位置(初始位置为给定的开始位置)
    int j=0; //设置子串的指针位置(初始位置为子串的首元素)
    
    while (S[i]!='\0')
    {
          if (T[j]=='\0') {return (i-j+1);} //比较到子串的’\0’,匹配成功
          if (S[i]==T[j]) {
             i++;
             j++;
            //子串与主串在该位的匹配值相等,则继续比较下一字符
          } else { //若不相同
            i=i-j+1; //主串回退到本次比较开始字符的下一字符 
            j=0; //模式串回退到首字符
          }
    }
    return 0; 比较到主串的’\0’,且此时子串的比较位不等于’\0’,匹配失败
}

KMP主程序代码:
int mystrstr(char* S, char* T, int pos, const int* next)
{
    int i=pos; //主串指针 
    int j=0; //模式串指针 
    
    while (S[i]!='\0') //当主串指针所指字符不为'\0'时,继续比较 
    {     
          
          if (j==-1) {i++;j++;}
          // 当头元素仍然不匹配时,j=-1,此时j指针清0指向模式串的首元素, i指针指下主串的下一元素 
          if (T[j]=='\0') {return (i-j+1);}
          // 当模式串指针所指元素为'\0'时,匹配完成,返回位置 
          if (S[i]==T[j]) {
             i++;
             j++;
             //当模式串指针与主串指针所指元素相同时,两指针都相加.比较下一元素 
          } else {
            j=next[j];
            //若模式串指针与主串指针所指内容不同时,模式串指针回退指到next[j]位置(第j位发生失配) 
          }
    }
    return 0;
}

生成next[]数组代码
//该程序用next[i]来推测next[i+1]
//每次比较开始时next[i]=k,每次比较开始前i与k成对应关系 
void GetNext (char* T,int* next)
{
     int j=0;
     int k=-1; //k为当第j位发生失配时,需要移动到的下一次进行比较的位(第k位)            
     next[0]=-1;
     //给定初始值,当比较到第一个元素(下标为0)仍然不等时,k的值为-1 
     
     while (j<strlen(T)) //j的大小有strlen(T)个,下标从0开始 
     {
           if (k==-1||T[k]==T[j])
           {
              //next[j]=k的定义为: t[0]...t[k-1]=t[j-k+1]...t[j-1] 
              //当T[k]=T[j]时,即T[next[j]]=T[j]时,T[1]...T[k]=T[j-k+1]...T[j],此时next[j+1]=next[j]+1=k+1,即可以求出next[j+1] 
              //当k=1时,即j+1的前一个元素与模式串的首元素相比,仍然不同,则应该让第j+1个元素直接与首元素进行比较 
              next[j+1]=k+1;
              j++; 
              k++; //k=next[j+1]=k+1,不能写k=next[j+1],因为上面一句j已经变化过了
              //next[j+1]=next[j]+1=k+1,即j+1与k+1是成对出现的 
              //下次比较开始前,j与k必须成对应关系出现, 满足这个式子:next[j+1]=k+1
           } else {
               k=next[k];
               //如果不等,可以理解为模式串的第k(next[j])位发生不匹配
               //则寻找到第next[k]位(保证k之前的元素匹配)继续进行比较
               }
     }
}

生成KMP改进算法的next[]数组代码
void GetNext (char* T,int* next)
{
     int j=0;
     int k=-1;

     next[0]=-1;
     // next[j]=k
     
     while (j<strlen(T))
     {
           if (k==-1||T[k]==T[j])
           {
              next[j+1]=k+1;
              
              if (T[j+1]==T[next[j+1]]) {
                 next[j+1]=next[next[j+1]];
              } 
              //就多了这段,当T[j+1]与T[next[j+1]]相等时,使next[j+1]=next[next[j+1]]
              j++;
              k++;
           } else {
               k=next[k];
               }
     }                 
}


本文来自CSDN博客,转载请标明出处:http://blog.csdn.net/ultrasurf/archive/2007/11/08/1873589.aspx

posted @ 2010-11-12 10:29 lzh525 阅读(781) | 评论 (0)编辑 收藏

2010年11月2日

     摘要:  !!!!比赛中被卡的题,超郁闷,一个细微没注意到的地方导致与奖项擦肩而过,遗憾啊....教训总结:(1)变量命名时尽量见词知意,不要去随便搞个字母去所谓的节约时间,这样可以避免变量搞混检查错误困难。 (2)平时要注意细节问题,遇到某些问题时还是要相信自己。 (3)团队合作,时间观念,全局观念很重要.... 1 #include<iostream...  阅读全文

posted @ 2010-11-02 19:38 lzh525 阅读(384) | 评论 (0)编辑 收藏

2010年10月24日

     摘要: 将军....棋盘搜索问题  阅读全文

posted @ 2010-10-24 09:14 lzh525 阅读(218) | 评论 (0)编辑 收藏

     摘要: //注意数组模板创建的重要性1 #include<stdio.h> 2 #include<string.h> 3 char s[15]; 4 char a[5][35]= 5 { "q-qq0qq-qq-qq0qq-qq-qq-qq-qq-q", 6 "|0|q0|q0|q0||0||0q|0qq0||0||0|", 7 "q0qq0qq...  阅读全文

posted @ 2010-10-24 09:05 lzh525 阅读(299) | 评论 (0)编辑 收藏

2010年10月16日

 1 /*并查集学习:
 2 
 3 并查集:(union-find sets)
 4 
 5 一种简单的用途广泛的集合. 并查集是若干个不相交集合,能够实现较快的合并和判断元素所在集合的操作,应用很多,如其求无向图的连通分量个数等。最完美的应用当属:实现Kruskar算法求最小生成树。
 6 
 7 l         并查集的精髓(即它的三种操作,结合实现代码模板进行理解):
 8 
 9 1、unit(x) 把每一个元素初始化为一个集合
10 
11 初始化后每一个元素的父亲节点是它本身,每一个元素的祖先节点也是它本身(也可以根据情况而变)。
12 
13 2、find(x) 查找一个元素所在的集合
14 
15 查找一个元素所在的集合,其精髓是找到这个元素所在集合的祖先!这个才是并查集判断和合并的最终依据。
16 判断两个元素是否属于同一集合,只要看他们所在集合的祖先是否相同即可。
17 合并两个集合,也是使一个集合的祖先成为另一个集合的祖先,具体见示意图
18 
19 3、connect(x,y) 合并x,y所在的两个集合
20 
21 合并两个不相交集合操作很简单:
22 利用find找到其中两个集合的祖先,将一个集合的祖先指向另一个集合的祖先。
23          并查集的优化
24 
25 1、find(x)时 路径压缩
26 寻找祖先时我们一般采用递归查找,但是当元素很多亦或是整棵树变为一条链时,每次find(x)都是O(n)的复杂度,有没有办法减小这个复杂度呢?
27 答案是肯定的,这就是路径压缩,即当我们经过"递推"找到祖先节点后,"回溯"的时候顺便将它的子孙节点都直接指向祖先,这样以后再次find(x)时复杂度就变成O(1)了,如下图所示;可见,路径压缩方便了以后的查找。
28 
29 
30 2、connect(x,y)时 按秩合并
31 即合并的时候将元素少的集合合并到元素多的集合中,这样合并之后树的高度会相对较小。
32 */
33 
34 #include<iostream>
35 using namesfatherace std;
36 
37 int father[30001];//各个元素的父节点数组
38 int h[30001];//哥哥元素的高度
39 
40 void Init(int n)
41 {
42     for(int i=0;i<n;i++)
43     {
44         father[i]=i;
45         h[i]=0;
46     }
47 }
48 
49 int find(int x)
50 {
51     if(x!=father[x])
52         father[x]=find(father[x]);
53     return father[x];
54 }
55 
56 void connect(int a,int b)
57 {
58     int x,y;
59     x=find(a);
60     y=find(b);
61     if(x==y)
62         return ;
63     if(h[x]<h[y])
64         father[x]=y;
65     else
66     {
67         if(h[x]==h[y])
68             h[x]++;
69         father[y]=x;
70     }
71 }
72 
73 int main()
74 {
75     int k,a,i,m,n,num,t,first;
76     Init(20);
77     cin>>k;
78     while(k--)
79     {
80         cin>>m>>n;
81         
82         connect(m,n);
83     }
84     for(i=1;i<=10;i++)
85     {
86         cout<<i<<"的父节点为: "<<father[i]<<"  高度:"<<h[i]<<endl;
87     }
88     return 0;
89 }

posted @ 2010-10-16 15:51 lzh525 阅读(2151) | 评论 (1)编辑 收藏

2010年9月8日

     摘要: 大明A+BTime Limit: 3000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 2316    Accepted Submission(s): 688Problem Descript...  阅读全文

posted @ 2010-09-08 08:36 lzh525 阅读(417) | 评论 (0)编辑 收藏

2010年8月30日

     摘要: /* 一个大整数的问题。首先想到了字符串处理的方法,将乘法换成除法来做;如下代码1实现提交后果然超时。后来发现不止如此,还有一些问题处理错误.,后来转换思路终于在代码2下AC了此题;*//* 代码1*/1#include<iostream> 2#include<string.h> 3using namespace std;&...  阅读全文

posted @ 2010-08-30 17:39 lzh525 阅读(508) | 评论 (0)编辑 收藏

2010年8月26日

 1#include<stdio.h>
 2int p[30001];
 3int h[30001];
 4
 5void Init(int n)
 6{
 7    for(int i=0;i<n;i++)
 8    {
 9        p[i]=i;
10        h[i]=0;
11    }

12}

13
14int find(int x)
15{
16    if(x!=p[x])
17        p[x]=find(p[x]);
18    return p[x];
19}

20
21void connect(int a,int b)
22{
23    int x,y;
24    x=find(a);
25    y=find(b);
26    if(h[x]>=h[y])
27    {
28        p[y]=x;
29        h[x]++;
30    }

31    else
32    {
33        p[x]=y;
34        h[y]++;
35    }

36}

37
38int main()
39{
40    int k,a,i,m,n,num,t,first;
41    while(scanf("%d%d",&m,&n))
42    {
43        if(m==0&&n==0)
44            return 0;
45        Init(m);
46        num=1;
47        while(n--)
48        {
49            scanf("%d",&k);
50            first=0;
51            for(i=1;i<=k;i++)
52            {
53                scanf("%d",&a);
54                if(first)
55                    connect(a,t);
56                first=1;
57                t=a;
58            }

59        }

60    for(i=1;i<m;i++)
61                if(find(0)==find(i))
62                    num++;    
63printf("%d\n",num);
64    }

65    return 0;
66}

posted @ 2010-08-26 20:51 lzh525 阅读(265) | 评论 (0)编辑 收藏