백준 1765 : 닭싸움 팀 정하기

문제 링크

1) 내 친구의 친구는 친구다
2) 내 원수의 원수는 친구다

이 두 가지를 이용해서 만들어질 수 있는 팀의 개수를 찾는 문제였다. 서로 친구이면 같은 팀에 들어가야 하고, 같은 팀에 속에 있는 사람들끼리도 모두 친구여야 하므로 disjoint set을 떠올릴 수 있었다. 내 원수의 원수는 친구이다 이외에 원수에 대한 것을 사용하지 않기 때문에, BFS를 통해 2)를 이용했을 때 추가되는 친구관계를 모두 추가해준 다음, 전체 친구관계에 대해서 union을 해주었다. union-find 자료구조를 이용하면 사실 BFS를 돌릴 필요가 없지만, 시간 복잡도를 계산했을 때 O(n^2)가 나와 추가적으로 고민하지 않고 구현했다.

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <vector>
#include <utility>

using namespace std;

typedef pair<int,int> pii;
typedef long long ll;

const int INF = 21 * 1e8;
const int MAX = 1e9;

vector<int> p;

int find(int a)
{
   if(p[a] != a) p[a] = find(p[a]);
   return p[a];
}

bool merge(int u,int v)
{
   u = find(u);
   v = find(v);

   if(u == v) return false;

   p[u] = v;

   return true;
}

vector<vector<int>> fedge;
vector<vector<int>> eedge;

int n,m;

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

   cin>>n>>m;

   fedge = eedge = vector<vector<int>>(n);

   for(int i= 0;i<n;i++)
   {
       p.push_back(i);
   }

   for(int i = 0;i<m;i++)
   {
       string s;
       int v1,v2;
       cin>>s>>v1>>v2;

       v1--; v2--;

       if(s[0] == 'E')
       {
           eedge[v1].push_back(v2);
           eedge[v2].push_back(v1);
       }
       else
       {
           fedge[v1].push_back(v2);
           fedge[v2].push_back(v1);
       }
   } 

   for(int i = 0;i<n;i++)
   {
       queue<int> q;
       q.push(i);

       vector<bool> visit(n,false);
       visit[i] = true;

       int cnt = 0;
       while(!q.empty())
       {
           int q_size = q.size();

           while(q_size--)
           {
               int cur = q.front();
               q.pop();

               if(cnt == 2)
               {
                   fedge[i].push_back(cur);
               }

               if(cnt < 2)
               {
                   for(auto next : eedge[cur])
                   {
                       if(!visit[next])
                       {
                           visit[next] = true;
                           q.push(next);
                       }
                   }
               }
               
           }

           if(cnt == 2) break;

           cnt++;
           
       }
   }

   for(int i = 0;i<n;i++)
   {
       queue<int> q;
       q.push(i);
       
       vector<bool> visit(n,false);
       visit[i] = true;

       while(!q.empty())
       {
           int cur = q.front();
           q.pop();

           for(auto next : fedge[cur])
           {
               if(!visit[next])
               {
                   visit[next] = true;
                   merge(i,next);
                   q.push(next);
               }
           }
       }
   }

   vector<int> visit(n,false);

   int ans = 0;
   for(int i = 0;i<n;i++)
   {
       if(!visit[find(i)])
       {
           visit[find(i)] = true;
           ans++;
       }
   }

   cout<<ans;
   
   return 0;
}