차수열
백준 마라톤 문제들을 풀다가 차수열이라는 태그가 붙은 문제들이 몇개 나와서 공부를 해보았다.
처음보는 단어라서 뭔가 했는데 어떤 그래프의 모든 정점 차수를 모아 만들어서 차수열(degree sequence)이라고 한다.
재밌어 보여서 태그가 붙어있는 모든 문제를 풀어보았고, 여러 그래프나 트리에서의 성질을 공부할 수 있었다.
공부한 이론, 성질과 문제 풀이를 간단하게 적어보려고 한다.
차수열 관련 이론
그래프와 차수의 관계
우선 차수와 그래프에서 가장 간단하게 판별이 가능한 특성이다.
그래프에서 정점의 차수는 그 정점에 접하는 간선의 개수이다.
방향 그래프에서는 진입 차수와 진출 차수로 구분할 수 있지만 우선 무방향 그래프일 때의 특성이다.
D_i를 i번째 정점에 대한 간선의 수라고 하면 그래프에 N개의 정점이 있을 때 0 <= D_i < N이어야 한다.
또, 하나의 간선은 두개의 정점을 이으므로 모든 D_i를 더하면 짝수여야한다.
단순 그래프를 기준으로 하면 모든 D_i의 합은 N(N-1)보다 작거나 같다.
주어진 그래프가 트리라고 하면 모든 D_i의 합은 2(N-1)이 된다.
Erdős–Gallai 정리
차수열로 그래프를 만들 수 있는지 확인할 때 이용하는 정리이다.
내림차순으로 정렬된 수열 (d_1,d_2,⋯,d_n)에 대해서
라는 조건을 만족하는지 확인하면 된다.
좌변은 상위 k개 정점의 요구 차수 합, 우변은 “서로 k(k−1)”(완전 그래프 K에서 가능한 내부 연결)
“나머지 정점들이 상위 k 정점과 맺을 수 있는 최대 간선 수(각각 최대 k)”의 합 상한이다.
즉, 상위 k개의 요구량이 전체가 허용하는 상한을 넘지 않는지 확인하는 것이다.
하벨-하키미 알고리즘 (Havel-Hakimi Algorithm)
참고 자료: https://gazelle-and-cs.tistory.com/102
이는 차수열을 가지고 그래프를 복원할 때 사용하는 방법이다.
우선 차수열을 내림차순으로 정렬을 한다.
정리 1. 단순 그래프의 차수열이 되기 위한 필요충분조건
1
2
3
내림차순으로 정렬된 수열 (d_1,d_2,⋯,d_n)이 어떤 단순 그래프의 차수열이 되기 위한 필요충분조건은
이 수열에서 d_1을 제외한 가장 앞의 d_1개의 수(즉, d_2,⋯,d_(d_1+1))에 각각 1을 뺸 수열인
다시 말해, (b_2,⋯,b_n):=(d_2−1,⋯,d_(d_1+1)−1,d_(d_1+2),⋯,an)이 어떤 단순 그래프의 차수열이 되는 것이다.
증명을 하면 우선 b_2부터 b_n까지를 차수열로 갖는 단순 그래프가 있을 때 d_1의 차수를 가지는 정점을 넣고서
b_2부터 b_(d_1+1)까지 하나씩 이어주면 단순 그래프가 완성이 된다.
그렇다면 반대로는 (d_1,d_2,⋯,d_n)를 차수열로 가진 그래프에서 d_1과 붙어있는 간선을 다 떼서 만들 그래프를 보자.
그러면 (b_2,⋯,b_n)를 차수열로 가지는 그래프를 만들 수 있다.
이를 통해서 하벨-하키미 알고리즘이 만들어진다.
내림차순으로 정렬된 양수이며 (1 <= d_i < N)로 이루어진 수열이 있을 때 위의 정리처럼 b수열을 만드는 과정을
재귀적으로 반복하면서 계속 성질이 유지된 채 연결하면서 만들 수 있다면 그래프를 복구할 수 있다.
수행 시간은 총 N번 재귀가 일어나고 과정마다 정렬하는 것이 필요하기에 NlogN의 시간이 걸린다.
그러므로 O(N^2logN)의 시간 복잡도를 가진다.
차수로 트리 가능 여부 판정과 복원
위에서 본 그래프 중 트리일 때는 판정과 복원을 하기 더 쉽다.
판정 방법은 모든 D_i의 합이 2*(N-1)이면서 D_i>=1이면 된다.
그리고 복구 방법은 D_i==1인 정점을 모두 큐에 넣고, 아직 남은 정점들과 이어준다.
트리는 반드시 리프 노드가 있기 때문에 D_i가 1인 정점이 존재한다.
위상 정렬에서 쓰는 방법처럼 큐에서 빼면서 남은 정점들과 이어주면서 그 정점들의 차수를 1씩 줄인다.
그렇게 줄였을 때 그 정점의 차수가 1이 된다면, 큐에서 뺀 정점과의 선을 끊으면 그 정점이 리프 노드라는 것이고
이 과정을 계속 반복하면 된다.
마지막에는 큐에 두개의 정점이 남게 되고 그 둘을 이어주면 트리를 복원할 수 있다.
원리는 트리의 생김새를 이해하면 쉽게 이해할 수 있는 것 같다.
문제
난이도 순으로
Y (S3, 31217)
그래프가 주어지고 그 중 4개의 정점을 선택했을 때 Y 형태로 정점 1개에 나머지 3개가 붙어있는 모양이
총 몇개인지 구하는 문제이다.
그래프의 모든 정점에 대해 차수를 구하고, 차수를 n이라 하면 n(n-1)(n-2)/6을 계산해 더하면 된다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
for(int i=0;i<m;i++){
cin >> a >> b;
v[a].push_back(b);
v[b].push_back(a);
}
ans=0;
for(int i=1;i<=n;i++){
int sz=v[i].size();
if(sz>=3){
ans+= sz*(sz-1)*(sz-2)/6;
}
ans%=mod;
}
cout << ans;
Парное пугание (G5, 28570)
n과 k가 주어지고 n명의 아이들은 각각 1번 또는 k번의 짝을 지어서 나가야 한다.
n명에 대해 있을 때 가능하다면 한번만 짝을 지어야하는 학생의 수를 출력하고 불가능하면 -1을 출력한다.
우선 가장 먼저 생각나는 것은 k+1개의 정점을 가진 star 형태의 그래프이다.
중심에 있는 아이는 k개의 짝을 지을 수 있고, 나머지 아이는 1번의 짝만 짓게 된다.
그렇게 확장을 시켜보면 가능한 그래프는 star에 star가 연결된 형태여야만 한다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
int main()
{
ios_base ::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
long long mod = 1'000'000'007;
using P=pair<int,int>;
long long a, b, c, d;
long long ans = 0;
cin >> n >> m;
if(n==m+1){
cout<<m;
return 0;
}
n-=(m+1);
if(n%(m-1)==0){
cout << m+n/(m-1)*(m-2);
}
else cout<<-1;
return 0;
}
Autobiography (G4, 31110)
각 테스트케이스에 대해 정점과 간선이 주어지고 무방향 그래프이다.
각 정점은 b또는 o의 알파벳을 가진다.
이 때 이어져있는 서로 다른 정점 4개를 골라 bobo를 만들 수 있는 경우의 수를 출력한다.
우선 그래프를 저장하는 것은 각각 b와 o인 정점끼리 주어졌을때만 저장을 한다.
그 다음 o인 정점들을 탐색하며 b에 연결되어 있는 것 1개와 나머지 b에 대한 간선 수를 곱해서 더한다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
while(cin >> n >> m >> s){
ans=0;
vector<bool> bb(n+1, 0);
vector<bool> oo(n+1, 0);
vector<map<int, int>> vm(n+1);
for(int i=0;i<s.size();i++){
if(s[i]=='b')bb[i+1]=1;
else oo[i+1]=1;
}
for(int i=0;i<m;i++){
cin >> a >> b;
if(bb[a] && oo[b] || bb[b]&&oo[a]){
vm[a][b]=1;
vm[b][a]=1;
}
// 서로 다른 그래프만 저장
}
ll tt;
for(int i=1;i<=n;i++){
if(oo[i]){
// o를 기준으로 연결된 것을 확인.
// b
for(auto at1:vm[i]){ //1번째 b와 3번째 b
ans +=(vm[i].size()-1)*(vm[at1.first].size()-1);
}
}
}
cout << ans << '\n';
}
Dr Who’s Banquet (G1, 11421)
차수열 (G1, 2084)
위의 두 문제는 같은 문제이다.
문제를 풀 때는 그리디인가? 하고서 증명을 하지 않고 풀었고
하벨 하키미 알고리즘을 통해서 증명까지 할 수 있다.
Road Network 2 (P5, 8286)
위의 트리 복원 방법을 그대로 적용하면 된다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
cin >> n;
vector<int> v(n+1);
queue<int> q;
ll tt=0;
for(int i=1;i<=n;i++){
cin>>v[i];
tt+=v[i];
if(v[i]==1)q.push(i);
}
if(n<=1 || tt!=2*(n-1)){
cout<<"BRAK";
return 0;
}
vector<int> tmp;
for(int i=1;i<=n;i++){
for(int j=0;j<v[i]-1;j++){
tmp.push_back(i);
}
}
for(int i=0;i<tmp.size();i++){
v[tmp[i]]--;
if(v[tmp[i]]==1) q.push(tmp[i]);
cout << tmp[i] << ' ' << q.front() <<'\n';
q.pop();
}
cout << q.front();
q.pop();
cout << ' ' << q.front();
return 0;
축구 게임 (P5, 13560)
역시 하벨 하키미 알고리즘으로 점수로 그래프를 만들 수 있는지 확인하면 된다.
N이 10000이지만 2초의 시간에 N^2logN을 허용해서 풀 수 있다.
비 오는 날 (P5, 23578)
우선 트리 구조이므로 차수의 합은 2(n-1)이다.
각 건물마다 최소 1개씩은 다리의 끝이 존재하므로 1개씩 놓으면 n-2개가 남는다.
이제 n-2개를 1개씩 어떤 건물에 더했을 때 이득일지 계산을 통해서 그리디하게 주면 된다.
수식을 통해서 관계를 간단하게 구할 수 있다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
cin >> n;
vector<ll> v(n+1);
priority_queue<P> pq;
for(int i=1;i<=n;i++){
cin>>v[i];
ans+=v[i]; //1씩을 넣어놓고
pq.push({-1*(v[i])*(2*1+1), 1});
}
//총 다리 개수는 n-1, 차수 총 합은 2*(n-1)
//1개 이상은 있어야 하고? n개보다는 작아야 하고
//a(2*i+1)이 작아야하는 듯? i는 기존 간선이고 a는 학생 수
for(int i=0;i<n-2;i++){
ll val = -1*pq.top().first;
ll cnt=pq.top().second;
pq.pop();
ans+=val;
ll stu=val/(2*cnt+1);
cnt++;
pq.push({-1*stu*(2*cnt+1), cnt});
}
if(n==1)ans=0;
cout << ans;
//2 2 1 1
//3 1 1 1
return 0;
Wireless is the New Fiber (P4, 15699)
트리 복원 방법과 성질을 이용하는 것이 섞인 문제였다.
차수가 바뀌는 노드의 개수가 최소여야 하므로 최대한 큰 것에서 빼야겠다고 생각했다.
목표는 2(n-1)이고, 주어진 차수의 총 합은 2*m이므로 빼야하는 수는 2(m-n+1)이다.
오름차순으로 정렬한 차수열에 대해 빼주면서 트리의 형태를 만들어 주고 복구하면 된다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
int main()
{
ios_base ::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
long long mod = 998'244'353;
using P=pair<ll,ll>;
long long a, b, c, d;
long long ans = 0;
cin >> n >> m;
vector<ll> cha(n, 0);
for(int i=0;i<m;i++){
cin >> a >> b;
cha[a]++;
cha[b]++;
}
// cha에서 총 빼야 하는 수가 2*(m-n+1)인거지.
int del = 2*(m-n+1); // 지울양.
vector<P> vp(n);
for(int i=0;i<n;i++){
vp[i]={cha[i], i};
}
sort(vp.rbegin(), vp.rend()); //큰거부터 빼고
// for(int i=0;i<n;i++){
// cout << vp[i].first << ' ';
// }cout<<'\n';
int cnt=0; // 달라지는 개수
for(int i=0;i<n;i++){
if(del>0){
cnt++;
if(del>vp[i].first-1){
del-=(vp[i].first-1); //최소 1개는 있어야해서
vp[i].first=1;
}
else{
vp[i].first-=del;
del=0;
}
}
else break;
}
// for(int i=0;i<n;i++){
// cout << vp[i].first << ' ' << vp[i].second << '\n';
// }cout<<'\n';
cout << cnt << '\n';
cout << n << ' ' << n-1 << '\n';
sort(vp.begin(), vp.end());
queue<int> one; //경로찍기
for(int i=0;i<n;i++){
if(vp[i].first==1){
one.push(vp[i].second);
}
else{
cout << one.front() << ' ' << vp[i].second << '\n';
one.pop();
if(--vp[i].first==1){ //1개 남으면 넣어
one.push(vp[i].second);
}
else i--;
}
}
cout << one.front()<< ' ';
one.pop();
cout << one.front() << '\n';
return 0;
}
Counting Friends (P3, 10020)
Erdős–Gallai 정리와 누적합을 이용해서 판별 할 수 있다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
cin >> n;
vector<P> v(n+1);
ll tt=0;
for(int i=0;i<n+1;i++){
cin>>v[i].first;
v[i].second=i+1;
tt+=v[i].first;
}
sort(v.rbegin(), v.rend());
vector<ll> nu(n+2, 0);
for(int i=1;i<n+2;i++){
nu[i]=nu[i-1]+v[i-1].first;
}
vector<int> ansv;
for(int i=0;i<n+1;i++){
flag=0;
int tmp=v[i].first;
long long cut = tt - tmp;
if(cut%2==1 || cut<0 || cut>1LL*n*(n-1)) continue;
vector<ll> deg;
for(int t=0;t<n+1;t++){
if(t==i) continue;
ll dval = v[t].first;
if(dval<0 || dval>n-1){
flag=1;
break;
}
deg.push_back(dval);
}
if(flag) continue;
vector<ll> S(n+1, 0);
for(int k=1;k<=n;k++) S[k]=S[k-1]+deg[k-1];
for(int j=0;j<n;j++){
int k=j+1;
long long na=0;
for(int t=k;t<n;t++){
na +=(deg[t]>=k?k:deg[t]);
}
long long rhs = 1LL*k*(k-1)+na;
if(S[k]>rhs){
flag=1;
break;
}
}
if(flag==0){
ansv.push_back(v[i].second);
}
}
cout << ansv.size() << '\n';
sort(ansv.begin(), ansv.end());
for(int i=0;i<ansv.size();i++){
cout << ansv[i] <<'\n';
}
return 0;
Best Tree (P2, 18459)
그래프의 차수열이 주어졌을 때 maximum matching을 구하는 문제다.
maximum matching은 정점쌍을 중복되지 않게 선택한 것들의 집합중 최대 크기이다.
우선 가장 많은 값을 가지는 그래프를 그리면 o-o-o-o-o 처럼 쭉 늘어진 그래프가 있다.
이 때는 N/2개의 쌍을 가질 수 있다.
그러고서 차수가 1인 리프 노드의 개수를 L이라고 놓자.
N>2인 그래프에서 각 간선의 한 쪽은 반드시 리프가 아니다.
그러면 리프가 아닌 정점은 한번만 매칭에 쓸 수 있으므로 N-L개보다 쌍이 많을 수 없다.
그러므로 min(N/2, N-L)개가 정답이 된다.
이 때 N=2일 때는 1개임에 주의해야 했다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int tc;
cin >> tc;
while(tc-->0){
cin >> n;
vector<int> v(n);
int cnt=0;
for(int i=0;i<n;i++){
cin>>v[i];
if(v[i]==1)cnt++;
}
if(n==2)cout<<1<<'\n';
else cout<<min(n/2, n-cnt) << '\n';
}
return 0;