連通図(すべてのエッジを入力し、図が連通しているかどうかを判断する)

3871 ワード

タイトルの説明:
無方向図とその中のすべてのエッジを与えて、この図がすべての頂点が連通しているかどうかを判断します.
入力:
各データ群の最初の行は2つの整数nとm(0<=n<=1000)である.nは図の頂点数を表し、mは図中の辺の数を表す.nが0であると入力が終了する.その後、m行のデータがあり、各行に2つの値xとy(0
出力:
入力データのセットごとに、すべての頂点が接続されている場合は「YES」、そうでない場合は「NO」が出力されます.
サンプル入力:
4 3 1 2 2 3 3 2 2 1 2 3 0サンプル出力:
NO
YES

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;


class UnionFind {
    int father[1001]; // 0 ~ 1000      /  
    int contain[1001]; //       
    int minIndex; //   
    int maxIndex; //   
    int cnt; //       

public :
    UnionFind() {}
    UnionFind(int minIndex, int maxIndex) {
        // 1 ~ 4
        this->minIndex = minIndex;
        this->maxIndex = maxIndex;
        this->cnt = maxIndex - minIndex + 1; //        

        for (int i = minIndex; i <= maxIndex ; i++) {
            father[i] = -1;
            contain[i] = 1;
        }

    }

    int getRoot(int x) {
        if (father[x] == -1) {
            return x;  //       
        } else {
            //      ，     
            //    set            ？
            int d = father[x];
            int root = getRoot(d);
            if (d != root) {
                father[x] = root; //    root  ，        
                contain[d] -= contain[x]; // contain  ，  root 
            }
            return root;
        }

    }

    bool isConnected(int x, int y) {
        return getRoot(x) == getRoot(y);
    }

    bool connect(int x, int y) {
        int xRoot = getRoot(x);
        int yRoot = getRoot(y);
        if (xRoot == yRoot) {
            //cout << "      set   " << endl;
            return false; //       set   ，             
        } else {
            if(contain[x] >= contain[y]) {
                // x     ， y  x
                father[yRoot] = xRoot;
                contain[xRoot] += contain[yRoot];
            } else {
                // y    ，x  y
                father[xRoot] = yRoot;
                contain[yRoot] += contain[xRoot];
            }
        }
        cnt --; //     1
    }

    int getCnt() {
        return cnt;
    }


    void show() {
        cout << "---    ---" << endl;
        cout << "father :";
        for (int i = minIndex; i <= maxIndex; i++) {
            cout << setw(4) << father[i] << "\t";
        }
        cout << endl;

        cout << "index  :";
        for (int i = minIndex; i <= maxIndex; i++) {
            cout << setw(4)  << i << "\t";
        }
        cout << endl << endl;


        cout << "contain :";
        for (int i = minIndex; i <= maxIndex; i++) {
            cout << setw(4)  << contain[i] << "\t";
        }
        cout << endl;

        cout << "index  :";
        for (int i = minIndex; i <= maxIndex; i++) {
            cout << setw(4)  << i << "\t";
        }
        cout << endl;

        cout << "---    ---" << endl << endl;
    }



};


int main() {
    int n, m; //       
    int x, y;
    while (cin >> n >> m && n != 0 && m != 0) {
        UnionFind uf(1,n);
        for (int i = 1; i <= m; i++) {
            cin >> x >> y;
            uf.connect(x, y);
        }
        if (uf.getCnt() == 1) {
            cout << "YES" << endl;
        } else {
            cout << "NO" << endl;
        }
    }

}

クラスを使ったほうがいいです.そうしないと、各ケースは内容を再リセットし、データが外に露出し、不快になります.

何もしなくても運が悪いとApacheは落ちる

xdebug+phpstorm+(chrome|postman)を使用してphpをデバッグ