- #include
- #defineMAXN 1050using namespace std;
- int pre[MAXN];
- intFind(int pos) {
- intr = pos;
- while(r != pre[r])
- r = pre[r];
- inti = pos;
- while(i != r) {
- intt = pre[i];
- pre[i] = r;
- i = t;
- }
- return r;
- }
- voidJoin(intposX,int posY) {
- introotX = Find(posX), rootY = Find(posY);
- if(rootX != rootY)
- pre[rootX] = rootY;
- }
- int main()
- {
- int N, M;
- while(cin >> N >> M && N) {
- intct =0;
- for(inti =1; i <= N; ++i)
- pre[i] = i;
- int cityA, cityB;
- while(M--) {
- cin >> cityA >> cityB;
- Join(cityA, cityB);
- }
- for(inti =1; i <= N; ++i)
- if(pre[i] == i)
- ct++;
- cout << ct -1<< endl;
- }
- return 0;
- }
来源: http://www.bubuko.com/infodetail-1976045.html