URI Online Judge | 1209
Festas de São Petersburgo
Por Marcio T. I. Oshiro, USP 
Brasil
Timelimit: 3 Brasil
São Petersburgo tornou-se após o fim da cortina de ferro, no início dos anos 90, uma das principais cidades da cena alternativa em todo o mundo. Grupos de punks, diversas bandas de hardcore e outros representantes da cena alternativa mudaram-se para a cidade, atraídas pela grande quantidade de jovens. Com o surgimento das comunidades virtuais, alguns anos mais tarde, notou-se o enorme potencial do uso destas comunidades para combinar encontros, festas, raves, etc.
Nestas festas de São Petersburgo é sempre muito importante que cada um dos participantes tenha pelo menos um certo número de amigos na rede social. E, ao mesmo tempo, desejamos convidar o maior número possível de pessoas de São Petersburgo desde que a restrição com relação ao número de amigos seja satisfeita. Tal restrição diz que, para ser convidada a festa, a pessoa precisa ter pelo menos um número K de amigos na lista de convidados.
Sua tarefa neste problema é, dado o conjunto de pessoas da comunidade e a lista de suas relações, determinar quais devem ser chamadas para que a festa tenha a maior quantidade possível de participantes satisfazendo a restrição.
Entrada
A entrada é composta por diversas instâncias e termina com final de arquivo (EOF). A primeira linha de cada instância contém três inteiros N (1 ≤ N ≤ 1000), M e K (O ≤ K ≤ N) representando respectivamente o número de pessoas na comunidade, o número de relações de amizade nessa comunidade e o número mínimo de amigos convidados uma pessoa precisa ter para ser convidada. Cada pessoa da comunidade é identificada por números de 1 a N. Cada uma das próximas M linhas contém um par de pessoas indicando que elas são amigas na rede social.
Saída
Para cada instância imprima uma única linha contendo a lista das pessoas a serem convidadas separadas por um espaço em branco. A lista deve estar ordenada em ordem crescente. Caso ninguém possa ser convidado, imprima o número 0.
#include <cstdio>
#define MAXN 1001
#define gc getchar_unlocked
void getint(int &x){
register int c = gc();
x = 0;
for(;(c<48 || c>57);c = gc());
for(;c>47 && c<58;c = gc()) {x = (x<<1) + (x<<3) + c - 48;}
}
int grau[MAXN],processado[MAXN],grafo[MAXN][MAXN],tamanho[MAXN];
int main(){
int n,m,k;
while(scanf("%d %d %d",&n,&m,&k) != EOF){
int possivel = 0;
for(int i=1;i<=n;i++){
grau[i] = 0;
processado[i] = 0;
tamanho[i] = 0;
}
while(m--){
int u,v;
getint(u);
getint(v);
grau[u]++;
grau[v]++;
grafo[u][tamanho[u]++] = v;
grafo[v][tamanho[v]++] = u;
}
for(int contador = 0; contador < n;contador++){
int vertice = -1, graumaximo = n + 20;
for(int i=1;i<=n;i++){
if(processado[i]) continue;
if(grau[i] < graumaximo){
graumaximo = grau[i];
vertice = i;
}
}
processado[vertice] = 1;
if(graumaximo >= k) break;
for(int i = 0; i < tamanho[vertice];i++){
int u = grafo[vertice][i];
grau[u]--;
}
}
for(int i=1;i<=n;i++){
if(grau[i] >= k){
if(possivel) printf(" ");
else possivel = 1;
printf("%d",i);
}
}
if(possivel == 0) printf("0");
printf("\n");
}
return 0;
}
0 Comentários