Ice_cream's world I

传送门

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

3

并查集的应用，用来查找被分割的区域个数。
即当两个节点值相同时说明已经为了一个圈，否则不可能，此时区域个数加1.

#include<iostream>
#include<vector>
using namespace std;
int set[100001];
int ans = 0;
int find(int x)  //寻找根结点
{
    return set[x] == x ? x : set[x] = find(set[x]);
}
void mix(int x, int y)
{
    int fx = find(x), fy = find(y);
    if (fx != fy)   //如果根结点不相同
        set[fx] = fy;
    else    //否则已经形成一个圈
        ans++;
}
int main()
{
    int n, m, a, b,x,y;
    while (cin >> n >> m)
    {
        ans = 0;
        for (int i = 0; i < n; i++) //初始化
            set[i] = i;
        for (int j = 0; j < m; j++)
        {
            cin >> a >> b;
            mix(a, b);
        }
        cout << ans << endl;
    }   
}