并查集

写在前面

并查集

#include <iostream>
#include <vector>

using namespace std;


int find_root(int indx,vector<int>& parent) {
    while(parent[indx]!=indx)
        indx = parent[indx];
    return indx;
}

void uni(int x,int y,vector<int>& parent) {
    x = find_root(x,parent);
    y = find_root(y,parent);
    if(x!=y) parent[x] = y;
}

int main() {
    int N,M;
    cin >> N >> M;
    if(N==0) {
        cout << "true" << endl;
        return 0;
    }

    vector<int> parent(N,0);
    for(int i=0;i<N;++i)
        parent[i] = i;

    vector<vector<int>> matrix(N,vector<int>(N,0));
    for(int i=0;i<M;++i) {
        int a,b;
        cin >> a >> b;
        matrix[a-1][b-1] = 1;
        matrix[b-1][a-1] = 1;
    }

    for(int i=0;i<N;++i) {
        for(int j=i+1;j<N;++j) {
            if(!matrix[i][j]) {
                uni(i,j,parent);
            }
            else {
                if(find_root(i,parent)==find_root(j,parent)) {
                    cout << "false" << endl;
                    return 0;
                }
            }
        }
    }
    cout << "true" << endl;
    return 0;
}