[アルゴリズム]白俊1043嘘

これはかなり大変な問題です.Union Findはアルゴリズムを知らず、解決策が思いつかない.

概要

真実を知っている人と同じパーティーにいる人は、真実を知っている人と同じになります.

に答える

最初は、嘘をつくパーティーを1にし、ないパーティーを0にすることで、すべての状況の数を探ろうとしました.従って時間的複雑度はO(2^n)となり,n<50ではこの問題を解決できない.
しかし,res変数をparty数としてうそをつかないpartyを見つけ出すと,−1で解決し,時間的複雑度がO(n^3)であれば,問題を解決できる.

ソースコード

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <utility>
#include <queue>
#include <map>
#include <vector>

using namespace std;

int parent[51];
vector<int> knowing;
vector<vector<int> > party(50);
int res,n,m,val = 0;

int Find(int x) {
    if (parent[x] == x)
        return x;
    return x = Find(parent[x]);
}

void Union(int x, int y) {
    x = Find(x);
    y = Find(y);
    parent[x] = y;
}

int answer() {
    int res = m;
    for(const vector<int> &people : party) {
        bool flag = false;
        for(const int &person : people) {
            if(flag) break; 
            for(const int &know : knowing) {
                if(Find(person) == Find(know)) {
                    flag = true;
                    break;
                }
            }
        }
        if(flag) {
            res--;
        }
    }
    return res;
}

int main() {
    scanf("%d %d",&n,&m);
    int tmp; 
    scanf("%d",&tmp);
    int a;
    for(int i = 0;i<n;i++) {
        parent[i] = i;
    }
    for(int i = 0;i<tmp;i++) {
        scanf("%d",&a);
        knowing.push_back(a);
    }
    for(int i = 0;i<m;i++) {
        scanf("%d",&tmp);
        int num,prev;
        for(int j = 0;j<tmp;j++) {
            if(j >= 1) {
                prev = num;
                scanf("%d",&num);
                Union(prev,num);
            }
            else {
                scanf("%d",&num);
            }
            party[i].push_back(num);
        }
    }
    printf("%d",answer());
}

リファレンス

東俊のブログ
実際、コードを学ぶように.😅 c++ではforeach文がどのように書かれているか分かりませんが、二分コードで知っています.c++11からサポートされているようです.