[백준 1043] 거짓말 (C#, C++) - soo:bak

문제 링크

1043번 - 거짓말

설명

여러 개의 파티가 있고 각 파티에 참석하는 사람들이 정해져 있으며, 일부 사람들은 이미 진실을 알고 있는 상황에서, 같은 파티에 참석한 사람들끼리는 진실 정보가 전파될 때, 거짓말을 할 수 있는 파티의 최대 개수를 구하는 문제입니다.

사람의 수와 파티의 수, 처음에 진실을 아는 사람들의 목록, 그리고 각 파티마다 참석하는 사람들의 목록이 주어집니다.

한 파티에 진실을 아는 사람이 한 명이라도 있으면 그 파티에서는 거짓말을 할 수 없습니다.

접근법

같은 파티에 참석한 사람들은 서로 진실 정보를 공유하게 되므로, 같은 파티 참석자들을 하나의 그룹으로 묶어야 합니다.

이를 위해 Union-Find 자료구조를 사용하여 각 사람이 속한 그룹을 효율적으로 관리하고, 같은 파티 참석자들의 그룹을 합칩니다.

모든 파티를 처리하고 나면, 처음에 진실을 아는 사람들이 속한 그룹을 별도로 표시합니다.

마지막으로 각 파티를 검사하여 진실을 아는 그룹에 속한 참석자가 한 명도 없는 파티의 개수를 세어주면 답이 됩니다.

예를 들어, 사람 1, 2, 3, 4가 있고 사람 1이 진실을 알며, 첫 번째 파티에 1과 2가 참석하고 두 번째 파티에 3과 4가 참석한다면, 첫 번째 파티는 1이 있어서 거짓말을 할 수 없지만 두 번째 파티는 거짓말을 할 수 있으므로 답은 1입니다.

만약 첫 번째 파티에 1과 2, 두 번째 파티에 2와 3이 참석한다면, 1-2가 연결되고 2-3이 연결되어 1, 2, 3 모두 같은 그룹이 되므로 두 파티 모두 거짓말을 할 수 없어 답은 0입니다.

---

Code

C#

using System;
using System.Collections.Generic;

namespace Solution {
  class UnionFind {
    private int[] parent;

    public UnionFind(int n) {
      parent = new int[n + 1];

      for (var i = 1; i <= n; i++)
        parent[i] = i;
    }

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

      return parent[x] = Find(parent[x]);
    }

    public void Union(int a, int b) {
      a = Find(a);
      b = Find(b);

      if (a != b) parent[a] = b;
    }

    public int Rep(int x) => Find(x);
  }

  class Program {
    static void Main(string[] args) {
      var first = Console.ReadLine()!.Split();
      var n = int.Parse(first[0]);
      var m = int.Parse(first[1]);

      var truthLine = Console.ReadLine()!.Split();
      var t = int.Parse(truthLine[0]);
      var truth = new List<int>();

      for (var i = 0; i < t; i++)
        truth.Add(int.Parse(truthLine[i + 1]));

      var uf = new UnionFind(n);
      var parties = new List<List<int>>(m);

      for (var i = 0; i < m; i++) {
        var line = Console.ReadLine()!.Split();
        var cnt = int.Parse(line[0]);
        var members = new List<int>(cnt);

        for (var j = 0; j < cnt; j++)
          members.Add(int.Parse(line[j + 1]));

        for (var j = 1; j < cnt; j++)
          uf.Union(members[0], members[j]);

        parties.Add(members);
      }

      var truthRep = new HashSet<int>();

      foreach (var tr in truth)
        truthRep.Add(uf.Rep(tr));

      var answer = 0;

      foreach (var p in parties) {
        var canLie = true;

        foreach (var person in p)
          if (truthRep.Contains(uf.Rep(person))) {
            canLie = false;
            break;
          }

        if (canLie) answer++;
      }

      Console.WriteLine(answer);
    }
  }
}

C++

#include <bits/stdc++.h>
using namespace std;

typedef vector<int> vi;
typedef vector<vi> vvi;

struct UnionFind {
  vi parent;

  UnionFind(int n) : parent(n + 1) {
    iota(parent.begin(), parent.end(), 0);
  }

  int find(int x) {
    return parent[x] == x ? x : parent[x] = find(parent[x]);
  }

  void unite(int a, int b) {
    a = find(a);
    b = find(b);

    if (a != b) parent[a] = b;
  }

  int rep(int x) {
    return find(x);
  }
};

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  int n, m; cin >> n >> m;

  int t; cin >> t;

  vi truth(t);

  for (int i = 0; i < t; i++)
    cin >> truth[i];

  UnionFind uf(n);
  vvi parties(m);

  for (int i = 0; i < m; i++) {
    int cnt; cin >> cnt;

    parties[i].resize(cnt);

    for (int j = 0; j < cnt; j++)
      cin >> parties[i][j];

    for (int j = 1; j < cnt; j++)
      uf.unite(parties[i][0], parties[i][j]);
  }

  unordered_set<int> truthRep;

  for (int tr : truth)
    truthRep.insert(uf.rep(tr));

  int answer = 0;

  for (auto& p : parties) {
    bool canLie = true;

    for (int person : p)
      if (truthRep.count(uf.rep(person))) {
        canLie = false;
        break;
      }

    if (canLie) ++answer;
  }

  cout << answer << "\n";

  return 0;
}