Ice_cream's world I--hdu2120

青旅半醒 2022-08-04 08:54 70阅读 0赞

Ice\_cream's world I

**Time Limit: 3000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)  
Total Submission(s): 839 Accepted Submission(s): 488**

Problem Description

ice\_cream's world is a rich country, it has many fertile lands. Today, the queen of ice\_cream wants award land to diligent ACMers. So there are some watchtowers are set up, and wall between watchtowers be build, in order to partition the ice\_cream’s world. But how many ACMers at most can be awarded by the queen is a big problem. One wall-surrounded land must be given to only one ACMer and no walls are crossed, if you can help the queen solve this problem, you will be get a land.

Input

In the case, first two integers N, M (N<=1000, M<=10000) is represent the number of watchtower and the number of wall. The watchtower numbered from 0 to N-1. Next following M lines, every line contain two integers A, B mean between A and B has a wall(A and B are distinct). Terminate by end of file.

Output

Output the maximum number of ACMers who will be awarded.  
One answer one line.

Sample Input

8 10

0 1

1 2

1 3

2 4

3 4

0 5

5 6

6 7

3 6

4 7

Sample Output

注意：这是一个求总共有多少环（环内有节点的不算），我们可以利用判断两节点的根节点是否相同来判断！

1 #include<stdio.h>
     2 #include<string.h>
     3 #include<algorithm>
     4 #define maxn 10010
     5 using namespace std;
     6 
     7 int per[maxn],sum;
     8 void init()
     9 {
    10     int i;
    11     for(i=0;i<maxn;i++)
    12     {
    13         per[i]=i;//初始化数组
    14     }
    15 }
    16 int find(int x)//查找根节点
    17 {
    18     int t=x;
    19     while(t!=per[t])
    20     t=per[t];
    21 return t;
    22 }
    23 void join(int x,int y)
    24 {
    25     int fx=find(x);
    26     int fy=find(y);
    27     if(fx==fy)
    28         sum++;//环的个数
    29     else
    30         per[fx]=fy;
    31 }
    32 int main()
    33 {
    34     int a,b,i,m,n;
    35     while(scanf("%d%d",&a,&b)!=EOF)
    36     {
    37         init();
    38         sum=0;
    39         for(i=0;i<b;i++)
    40         {
    41             scanf("%d%d",&m,&n);
    42             join(m,n);
    43         }
    44         printf("%d\n",sum);
    45     }
    46 return 0;
    47 }