题目1526：朋友圈-白红宇

题目1526：朋友圈

阅读量：4581 次

发布时间：2019-06-09

本文共 1451 字，大约阅读时间需要 4 分钟。

题目描述：

假如已知有n个人和m对好友关系（存于数字r）。如果两个人是直接或间接的好友（好友的好友的好友...），则认为他们属于同一个朋友圈，请写程序求出这n个人里一共有多少个朋友圈。
假如：n = 5 ， m = 3 ， r = {

{1 , 2} , {2 , 3} , {4 , 5}}，表示有5个人，1和2是好友，2和3是好友，4和5是好友，则1、2、3属于一个朋友圈，4、5属于另一个朋友圈，结果为2个朋友圈。

输入：

输入包含多个测试用例，每个测试用例的第一行包含两个正整数 n、m，1=<n，m<=100000。接下来有m行，每行分别输入两个人的编号f，t（1=<f，t<=n），表示f和t是好友。当n为0时，输入结束，该用例不被处理。

输出：

对应每个测试用例，输出在这n个人里一共有多少个朋友圈。

样例输入：

5 31 22 34 53 31 21 32 30

样例输出：

1 #include 
       
          //1526 2 #include 
         3 #include 
         
           4 #include 
          
            5 #include 
           
             6 #include 
            
              7 #include 
             
               8 #include 
              
                9 #include 
               
                10 #include 
                
                 11 #include 
                 
                  12 #include 
                  
                   13 #include 
                   
                    14 #include 
                    
                     15 #include 
                     
                      16 #include 
                      
                       17 #include 
                       
                        18 #include 
                        
                         19 #include 
                         
                          20 21 using namespace std;22 23 24 25 26 const int MAX = 100005;27 28 int pre[MAX];29 30 int Ans;31 32 33 34 35 int find(int x)36 { 37 int r = x; 38 while(pre[r] != r) 39 r = pre[r]; 40 int i = x; 41 int j; 42 while(i != r) 43 { 44 j = pre[i]; 45 pre[i] = r; 46 i = j; 47 } 48 49 return r;50 }51 void Merge(int x,int y)52 {53 int xf = find(x);54 int yf = find(y);55 if(xf != yf)56 {57 pre[xf] = yf;58 --Ans;59 }60 }61 62 int main()63 {64 int N,M,i,x,y;65 66 while(cin >> N >> M)67 {68 if(N == 0) 69 break;70 71 Ans = N; 72 73 for(i = 1;i <= N; ++i) 74 pre[i] = i;75 76 while( M-- )77 {78 cin >> x >> y;79 Merge(x,y);80 }81 82 cout<
                          
                           <

转载于:https://www.cnblogs.com/chchche/p/3466022.html

你可能感兴趣的文章