백준 1043번 거짓말(C++)🚩

어렵다.... 

 

각 파티의 참석인원을 모두 체크해서 무리를 짓고 진실이어야만 하는 무리 체크 후 파티에서 한명만 뽑아서 그 친구의 루트 노드가 진실인지를 판별하면된다. 

진실인지를 parent로 한번에 구현할수 있나? 고민하다 꼬여버리고 되는지는 잘 모르겠다. 어렵다..

 

#include <iostream>
#include<vector>
#include<map>

using namespace std;

vector<int>parent; 
vector<int>truth;

int find(int node){
    
    if(parent[node]<0){
        return node; 
    }
    
    return parent[node]=find(parent[node]);
}

void unions(int x,int y){
    
    int xp=find(x);
    int yp=find(y);
    
    if(xp==yp)return;
    
    if(truth[xp] || truth[yp]){
       truth[xp]=truth[yp]=true; 
    }
    
    if(parent[xp]<parent[yp]){
        parent[yp]=xp;
        
    }
    else if(parent[yp]<=parent[xp]){
        parent[xp]=yp;
    }
}


int main()
{
  int n,m; 
  int t,p;
  
  cin>>n>>m; 
  
  cin>>t;
  parent.assign(n+1,-1);
  truth.assign(n+1,0);
  
  for(int i=0;i<t;i++){
      cin>>p;
      truth[p]=1; //진실 아는사람 
  }
 /* 
  if(p==0){
      cout<<m;return 0;
  } 
  */
  int num,q;
  int ans=0; 
 
  //거짓말 파티 갯수 
  //진실 아는사람 있으면 무조건 진실 
  //진실 들은적 있는 사람이면 진실 
  
  //거짓 들은 사람 있으면 거짓해야함 
  //아무것도 들은적 없+거짓들은사람 -> 거짓
  
  //나중에 거짓으로 들통나는것도 안됨 
  vector<int>party;
  
  for(int i=0;i<m;i++){ //파티 케이스 
      cin>>num;
      
      cin>>q;
      int first=q; 
      party.push_back(first);
      
      for(int j=1;j<num;j++){
          cin>>q;
          
          unions(first,q); 
      }
  }
   
  for(int i=0;i<party.size();i++){
     if(truth[find(party[i])]==0)ans++;
  }
  
 
  cout<<ans; 
  
  
  return 0;
}