M27306: 植物观察

disjoint set, bfs, http://cs101.openjudge.cn/practice/27306/

思路：典型二分图判断

cpp

#include <iostream>
#include <vector>
using namespace std;

const int MAX_N = 105;  
int parent[MAX_N];     
int relation[MAX_N];    
void init(int n) {
    for (int i = 0; i < n; ++i) {
        parent[i] = i;  
        relation[i] = 0; 
    }
}
int find(int x) {
    if (parent[x] != x) {
        int origin_parent = parent[x];
        parent[x] = find(parent[x]); 
        relation[x] ^= relation[origin_parent];
    }
    return parent[x];
}

int main() {
    int n, m;
    cin >> n >> m;
    init(n);
    bool possible = true;  
    for (int i = 0; i < m; ++i) {
        int a, b, op;
        cin >> a >> b >> op;
        int root_a = find(a);
        int root_b = find(b);
        if (root_a == root_b) {
            if ((relation[a] ^ relation[b]) != op) {
                possible = false;
            }
        } else {
            parent[root_b] = root_a;
            relation[root_b] = relation[a] ^ relation[b] ^ op;
        }
    }
    cout << (possible ? "YES" : "NO") << endl;
    return 0;
}

思路：和LC886 可能的二分法一样，唯一不同的就是不仅要求某两个不在一组，还要求某两个在一组。

cpp

#include<iostream>
#include<vector>
#include<queue>
#include<algorithm>
using namespace std;
int find(vector<int>& parent,int i){
    if(i!=parent[i]){
        return find(parent,parent[i]);
    }
    return i;
}
void Union(vector<int>& parent,int i,int j){
    parent[find(parent,i)]=find(parent,j);
}
int main(){
    int n,m;
    cin>>n>>m;
    int flag=1;
    vector<vector<int>>different(n);
    vector<int>parent(n);
    for(int i=0;i<n;i++){
        parent[i]=i;
    }
    for(int i=0;i<m;i++){
        int p,q,r;
        cin>>p>>q>>r;
        if(r==0){
            Union(parent,p,q);
        }
        else{
            different[p].push_back(q);
            different[q].push_back(p);
        }
    }
    for(int i=0;i<n;i++){
        if(different[i].size()==0) 
        {continue;}
        int p=find(parent,i);
        int q=find(parent,different[i][0]);
        if(q==p)
        {
            flag=0;
            break;
        }
        if(different[i].size()>=2)
        {
            for(int j=1;j<different[i].size();j++)
            {
                if(find(parent,i)==find(parent,different[i][j])) {
                    flag=0;
                    break;
                }
                Union(parent,different[i][0],different[i][j]);
            } 
            if(flag==0) break;  
        }
    }
    if (flag==1){
        cout<<"YES";
    }
    else{
        cout<<"NO";
    }
    return 0;
}

M27306: 植物观察 ​

​

M27306: 植物观察