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 ≤ 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

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;

}
Copy The Code & Try With Live Editor

Input

x
+
cmd
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

Output

x
+
cmd
2 4 6
0
Advertisements

Demonstration


Previous
#1206 Beecrowd Online Judge Solution 1206 Challenge of St. Petersburg Solution in C, C++, Java, Js and Python
Next
#1216 Beecrowd Online Judge Solution 1216 Getline One Solution in C, C++, Java, Js and Python