[URI ONLINE JUDGE] – 1209 – St. Petersburg Parties

Link: https://www.urionlinejudge.com.br/judge/en/problems/view/1209

St. Petersburg became after the end of the Iron Curtain in the early ’90s, one of the main cities of the alternative scene worldwide. Groups of punks, hardcore bands and several other representatives of the alternative scene moved to the city, attracted by the large amount of young people. With the emergence of virtual communities, a few years later, it was noted the enormous potential of using these communities to combine meetings, parties, raves, etc..

In these celebrations of St. Petersburg is always very important that each participant has at least a certain number of friends on the social network. At the same time, we want to invite as many people as possible to St. Petersburg since the restriction on the number of friends is satisfied. This constraint says that, to be invited to the party, the person must have at least one number K of friends on the guest list.

Your task in this problem is, given the number of people in the community and to list their relationships, determine what should be called to the party that has the largest possible number of participants satisfying the constraint.

Input

The input have many test cases and ends with the end of file (EOF). The first line of each test case contains three integers N (1 ≤ N ≤ 1000), M and K (O ≤ KN) representing respectively the number of people in the community, the number of friendships in this community and the minimum number of friends asked a person must have to be invited. Each person in the community is identified by numbers from 1 to N. Each of the next M lines of the test case contains a pair of people indicating that they are friends in the social network.

Output

For each test case print a single line containing the list of people to invite separated by a blank space. The list should be sorted in ascending order. If anyone can be invited, print the number 0.

Sample Input Sample Output
6 6 2
1 3
3 5
2 3
2 4
4 6
6 2
6 6 3
1 2
2 3
3 1
4 5
5 6
6 4
2 4 6
0

solution:

<br />#include <stdlib.h>
#include <stdio.h>
#include <algorithm>
#include <vector>
#include <map>

using namespace std;

int main() {
int n, m, k;

while (scanf("%d %d %d\n", &n, &m, &k) != EOF) {
vector<int> aaa(n+1);
vector<vector<int>* > *am =
new vector<vector<int>* >(n+1);

for (int i = 1; i <= n; i++) {
aaa[i] = 0;
(*am)[i] = new vector<int>;
}

for (int j = 0; j < m; j++) {
int a, b;
scanf("%d %d\n", &a, &b);
aaa[a]++;
aaa[b]++;
(*am)[a]->push_back(b);
(*am)[b]->push_back(a);
}

map<int, bool> T;
bool cont = true;
while(cont) {
cont = false;
for (int i = 1; i < n+1; i++) {
if (T.count(i) == 0) {
int o = 0;
for (int j = 0; j < (*am)[i]->size(); j++) {
if (T.count((*am)[i]->at(j)) == 0)
o += 1;
}

if (o < k) {
cont = true;
T[i] = false;
for (int j = 0; j < (*am)[i]->size(); j++) {
aaa[(*am)[i]->at(j)] -= 1;
}
}
}
}
}

vector<int> s;
for (int i = 1; i < n+1; i++) {
if (T.count(i) == 0) {
s.push_back(i);
}
}

sort(s.begin(), s.end());
for (int i = 0; i < s.size(); i++) {
if (i == (s.size()-1))
printf("%d", s[i]);
else
printf("%d ", s[i]);
}
if(s.size() == 0) printf("0");
printf("\n");
}

return 0;
}

 

 

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s