|
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
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
|
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstring>
#include <vector>
#define MAXL 5
#define MAXF 10
using namespace std;
int n;
vector<vector<bool>> dead;
vector<int> graph[10004];
int ptr[10004];
struct info {
int cnt;
int id;
};
bool operator < (const info& a, const info& b)
{
if (a.cnt == b.cnt)
return a.id > b.id;
return a.cnt < b.cnt;
}
vector<info> Top5[10004];
void init(int N)
{
n = N;
memset(ptr, 0, sizeof(ptr));
dead.resize(n + 1, vector<bool>(n + 1, false));
for (int i = 1; i <= N; i++) {
graph[i].clear();
Top5[i].clear();
}
}
void add(int id, int F, int ids[MAXF])
{
for (int i = 0; i < F; i++)
{
graph[id].push_back(ids[i]);
graph[ids[i]].push_back(id);
dead[id][ids[i]] = false;
dead[ids[i]][id] = false;
}
}
void del(int id1, int id2)
{
dead[id1][id2] = true;
dead[id2][id1] = true;
}
void push(int host, int id, int num)
{
int idx = ptr[host];
Top5[host][idx] = { num, id };
idx++;
for (int i = idx - 2; i >= 0; i--)
{
if (Top5[host][i] < Top5[host][i + 1])
{
info tmp = Top5[host][i];
Top5[host][i] = Top5[host][i + 1];
Top5[host][i + 1] = tmp;
}
}
if (idx > 5)
idx = 5;
ptr[host] = idx;
}
int recommend(int id, int list[MAXL])
{
bool friendChk[10004] = { false, };
vector<int> isFriend;
for (int i = 0; i < graph[id].size(); i++)
{
if (!(dead[id][graph[id][i]])) {
isFriend.push_back(graph[id][i]);
friendChk[graph[id][i]] = true;
}
}
int friendCnt[10004];
memset(friendCnt, 0, sizeof(friendCnt));
vector<int> newFriend;
for (int i = 0; i < isFriend.size(); i++)
{
//cout << "friend list" << '\n';
for (int j = 0; j < graph[isFriend[i]].size(); j++)
{
//cout << graph[isFriend[i]][j].f_id << ' ';
if ((graph[isFriend[i]][j] == id) || (friendChk[graph[isFriend[i]][j]]) || (dead[isFriend[i]][graph[isFriend[i]][j]]))
continue;
if (friendCnt[graph[isFriend[i]][j]] == 0)
newFriend.push_back(graph[isFriend[i]][j]);
friendCnt[graph[isFriend[i]][j]] += 1;
}
//cout << '\n';
}
/*for (int i = 1; i <= 8; i++)
cout << friendCnt[i] << ' ';
cout << '\n';*/
if (newFriend.size() == 0)
return 0;
ptr[id] = 0;
Top5[id].clear();
Top5[id].resize(6);
for (int i = 0; i < newFriend.size(); i++)
{
push(id, newFriend[i], friendCnt[newFriend[i]]);
}
cout << "answer is " << '\n';
for (int i = 0; i < ptr[id]; i++)
{
cout << Top5[id][i].id << ' ';
list[i] = Top5[id][i].id;
}
cout << '\n' << '\n';
return ptr[id];
}
|
cs |
'Heap & 우선순위 큐' 카테고리의 다른 글
| 가운데를 말해요 (0) | 2024.02.27 |
|---|---|
| (중요!!!) 연산자 오버로딩 및 Heap 직접 구현 (0) | 2024.02.17 |
| Social Media (0) | 2024.02.12 |
| 카드 정렬하기 (1) | 2024.02.11 |
| 뉴스 알림 (0) | 2024.02.06 |