[백준 1765] 닭싸움 팀 정하기 (C#, C++) - soo:bak

문제 링크

1765번 - 닭싸움 팀 정하기

설명

친구와 원수 관계를 고려해 만들 수 있는 팀의 최대 개수를 구하는 문제입니다.

접근법

각 학생에 대해 친구와 원수 관계를 그래프로 저장합니다.

학생을 순서대로 방문하며, 아직 방문하지 않은 학생이면 새 팀으로 카운트합니다.

친구는 같은 팀이므로 바로 방문 처리하고, 원수의 원수도 친구이므로 함께 방문 처리합니다.

Code

C#

using System;
using System.Collections.Generic;

class Program {
  static void Main() {
    var n = int.Parse(Console.ReadLine()!);
    var m = int.Parse(Console.ReadLine()!);
    var v = new List<(char r, int idx)>[n + 1];
    for (var i = 0; i <= n; i++)
      v[i] = new List<(char, int)>();
    var isVisited = new bool[n + 1];

    for (var i = 0; i < m; i++) {
      var line = Console.ReadLine()!.Split();
      var r = line[0][0];
      var idx1 = int.Parse(line[1]);
      var idx2 = int.Parse(line[2]);
      v[idx1].Add((r, idx2));
      v[idx2].Add((r, idx1));
    }

    var ans = 0;
    for (var i = 1; i <= n; i++) {
      if (!isVisited[i]) ans++;
      isVisited[i] = true;
      for (var j = 0; j < v[i].Count; j++) {
        if (v[i][j].r == 'F') isVisited[v[i][j].idx] = true;
        else {
          for (var k = 0; k < v[v[i][j].idx].Count; k++)
            if (v[v[i][j].idx][k].r == 'E')
              isVisited[v[v[i][j].idx][k].idx] = true;
        }
      }
    }
    Console.WriteLine(ans);
  }
}

C++

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

typedef pair<char, int> pci;

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

  int n, m;
  if (!(cin >> n >> m)) return 0;
  vector<pci> v[1001];
  bool isVisited[1001] = {false, };

  for (int i = 0; i < m; i++) {
    char r; cin >> r;
    int idx1, idx2; cin >> idx1 >> idx2;
    v[idx1].push_back({r, idx2});
    v[idx2].push_back({r, idx1});
  }

  int ans = 0;
  for (int i = 1; i <= n; i++) {
    if (!isVisited[i]) ans++;
    isVisited[i] = true;
    for (size_t j = 0; j < v[i].size(); j++) {
      if (v[i][j].first == 'F') isVisited[v[i][j].second] = true;
      else {
        for (size_t k = 0; k < v[v[i][j].second].size(); k++)
          if (v[v[i][j].second][k].first == 'E')
            isVisited[v[v[i][j].second][k].second] = true;
      }
    }
  }
  cout << ans << "\n";

  return 0;
}