Algorithm
Problem Name: 2 AD-HOC - beecrowd | 1209
Problem Link: https://www.beecrowd.com.br/judge/en/problems/view/1209
St. Petersburg Parties
By Marcio T. I. Oshiro, USP 
Brazil
Timelimit: 3
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 ≤ K ≤ N) 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 |
2 4 6 |
Code Examples
#1 Code Example with C Programming
Code -
C Programming
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define true 1
#define false 0
#define MAXSIZE 1010
int f[MAXSIZE];
char vis[MAXSIZE];
char adj[MAXSIZE][MAXSIZE];
int main(int argc, char **argv)
{
int u, v, i;
int n, m, k;
while (scanf("%d %d %d", &n, &m, &k) != EOF)
{
memset(f, 0, sizeof(f));
memset(vis, 0, sizeof(vis));
memset(adj, 0, sizeof(adj));
for (i = 0; i < m; ++i)
{
scanf("%d %d", &u, &v);
adj[u][v] = adj[v][u] = true;
++f[u], ++f[v];
}
int e, s;
e = s = 0;
int queue[MAXSIZE << 2];
for (i = 1; i < = n; ++i)
if (f[i] < k)
queue[e++] = i, vis[i] = true;
while (s < e)
{
u = queue[s++];
for (i = 1; i < = n; ++i)
if (adj[u][i])
if (!vis[i] && --f[i] < k)
queue[e++] = i, vis[i] = true;
}
int ans[MAXSIZE];
for (i = 1, k = 0; i < = n; ++i)
if (!vis[i])
ans[k++] = i;
if (k)
for (i = 0; i < k; ++i)
printf("%d%c", ans[i], i < k - 1 ? ' ' : '\n');
else
puts("0");
}
return 0;
}
Input
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
Output
0