백준 11061 Awkward Group
https://www.acmicpc.net/problem/11061
위 사진처럼 모든 노드가 하나의 간선으로 연결되어 있는 그래프를 완전 그래프라고 정의한다.
완전그래프 내부 간선의 가중치들이 완전그래프와 연결되어 있는 외부 간선의 가중치보다 모두 작도록 만들 수 있는 완전그래프의 개수를 찾는 문제이다.
대략적인 알고리즘은 다음과 같다.
-
가중치가 작은 간선부터 양 쪽 노드를 그룹화 한다. (union-find 알고리즘)
-
그룹화된 간선의 개수(e), 노드의 개수(n)를 확인하여 nC2==e라면 완전그래프이다.
하지만 이러한 알고리즘에서는 가중치가 같은 간선이 여러개일때 처리 순서가 문제가 된다.
가중치가 같은 간선들이 있다면 그 간선들을 모두 그룹화 해준 뒤에 새로 생긴 완전그래프가 있는지 확인해주면 된다. (외부 간선과 내부 간선의 가중치가 같아도 완전그래프가 아니기 때문이다.)
이제 코드를 보자.
#include<bits/stdc++.h>
#define ff first
#define ss second
using namespace std;
const int SZ=1005;
int par[SZ]; // union find 를 위한 부모 저장
int ch[SZ]; // 완전 그래프 판별용 노드의 개수
int ln[SZ]; // 완전 그래프 판별용 간선의 개수
priority_queue<pair<int,pair<int,int>>> pq;
int find(int x){
if(x==par[x]) return x;
return par[x]=find(par[x]);
}
void merge(int x, int y){
x=find(x); y=find(y);
if(x==y){
ln[x]++;
return;
}
if(x>y) swap(x,y);
par[y]=x;
ch[x]+=ch[y];
ln[x]+=(ln[y]+1);
ch[y]=0; ln[y]=0;
}
bool isfull(int x){
x=find(x);
int a=ch[x], b=ln[x];
if(a*(a-1)==2*b) return true;
return false;
}
int main(void){
ios::sync_with_stdio(false); cin.tie(NULL);
int t; cin>>t;
while(t--){
int n; cin>>n;
for(int i=1;i<=n;i++){
par[i]=i;
ch[i]=1;
ln[i]=0;
}
for(int i=1;i<n;i++){
for(int j=i+1;j<=n;j++){
int x; cin>>x;
pq.push({-x,{i,j}});
}
}
int ans=0;
while(!pq.empty()){
vector<pair<int,pair<int,int>>> tv;
int tmp=pq.top().ff;
while(!pq.empty() && tmp==pq.top().ff){
tv.push_back(pq.top()); pq.pop();
}
if(tv.size()==1){
merge(tv[0].ss.ff,tv[0].ss.ss);
if(isfull(tv[0].ss.ff)) ans++;
}
else{
vector<pair<int,int>> chv;
for(int i=0;i<(int)tv.size();i++){
merge(tv[i].ss.ff,tv[i].ss.ss);
chv.push_back({tv[i].ss.ff,tv[i].ss.ss});
}
for(int i=0;i<(int)chv.size();i++){
chv[i]={find(chv[i].ff),find(chv[i].ss)};
}
sort(chv.begin(),chv.end());
chv.resize(distance(chv.begin(),unique(chv.begin(),chv.end())));
for(int i=0;i<(int)chv.size();i++){
if(isfull(chv[i].ff)) ans++;
}
}
}
cout<<ans-1<<'\n';
}
return 0;
}
완전그래프가 된 그래프를 중복해서 세는 일이 없도록 unique(),resize() 함수를 이용하여 중복된 원소를 제거하였다.
