upas.cpp

#include<bits/stdc++.h>
using namespace std;

const int MAXN =  112345;

vector<int> upanaocomb[MAXN]; //guardaremos as relacoes entre upas em um vetor de vectors,
							  // muito como em um grafo.
bool marc[MAXN]; //vetor de marcacao, descrito na explicacao

int n, m, totaldeupas = 0;

int main(){
	scanf("%d %d", &n, &m);

	for(int i = 0; i < m; i++){
		int u, v;
		scanf("%d %d", &u, &v);
		upanaocomb[u].push_back(v);
		upanaocomb[v].push_back(u);
	}

	for(int i = n; i > 0; i--){
		if(!marc[i]){
			// se a upa i ainda nao foi marcada,
			// ela nao afetara nenhuma upa com valor maior que o dela
			// e com certeza, é melhor usar ela do que qualquer upa que nao combina com ela
			totaldeupas++;

			for(int j = 0; j < upanaocomb[i].size(); j++){
				int upa = upanaocomb[i][j];
				marc[upa] = true;
			}

		}
	}
	printf("%d\n", totaldeupas);
	for(int i = 1; i <= n; i++){
		// imprimimos todas as upas nao marcadas
		if(!marc[i]){
			printf("%d ", i);
		}
	}
	printf("\n");


}