Seletiva IOI 2013

ilhas.cpp

// Ivan Carvalho
// Ilhas - Seletiva IOI - OBI 2013
#include <bits/stdc++.h>
#define MAXN 1010
int U[MAXN*MAXN],V[MAXN*MAXN],reservado[MAXN],pai[MAXN],peso[MAXN],pares[MAXN];
int find(int x){
	if (x==pai[x]) return x;
	return pai[x] = find(pai[x]);
}
void join(int x, int y){
	x = find(x);
	y = find(y);
	if (x==y) return;
	if (peso[x]< peso[y]) pai[x] = y;
	else if(peso[x] > peso[y]) pai[y] = x;
	else {
		pai[x] = y;
		peso[y]++;
	}
}
int main(){
	int n,b,p;
	scanf("%d %d %d",&n,&b,&p);
	for(int i=1;i<=n;i++) pai[i] = i;
	for(int i=1;i<=b;i++) scanf("%d %d",&U[i],&V[i]);
	for(int i=1;i<=p;i++){
		int davez;
		scanf("%d",&davez);
		reservado[davez] = 1;
	}
	int conjuntos = n - p;
	for(int i=1;i<=b;i++){
		if (reservado[U[i]] && reservado[V[i]]) continue;
		if (reservado[U[i]]){
			pares[U[i]]++;
			continue;
		}
		if (reservado[V[i]]){
			pares[V[i]]++;
			continue;
		}
		if (find(U[i]) != find(V[i])){
			join(U[i],V[i]);
			conjuntos--;
		}
	}
	if (conjuntos != 1){
		printf("N\n");
		return 0;
	}
	for(int i=1;i<=n;i++) if (reservado[i] && !pares[i]){
		printf("N\n");
		return 0;
	}
	printf("S\n");
	return 0;
}