Um union-find, ou conjunto disjunto (disjoint-set), é uma estrutura de dados que armazena conjuntos disjuntos de elementos.
Esta estrutura de dados possui as seguintes operações:
Esta estrutura de dados é interessante porque é possível resolver com ela diversos problemas no UVa (já veremos um exemplo) e porque com uma correta implementação as operações são muito rápidas. É possível mostrar que a complexidade amortizada de cada operação é, para todos os efeitos práticos, O(1).
Leiam a secção 2.4.2 do livro do Halim para ver alguns exemplos de execução. Se quiserem saber mais vejam a entrada na wikipedia ou o capítulo 21 do livro do Cormen que possui o pseudo-código que inspirou a implementação Java que se segue:
public class Union_Find {
/* The graph is represented as a forest of n-ary trees,
which result in a linear search of a node
(check details on CORMEN et al., chp.21) */
int[] p, // p[i] is the representative of i
rank; // rank[i] is the height upper bound of i
public Union_Find(int nNodes) {
rank = new int[nNodes]; // auto init to zero
p = new int[nNodes];
for(int i=0;i<p.length;i++)
p[i]=i;
}
public int findSet(int x) {
if (x!=p[x])
p[x] = findSet(p[x]);
return p[x];
}
public void union(int x, int y) {
link(findSet(x), findSet(y));
}
private void link(int x, int y) {
if (rank[x] > rank[y])
p[y] = x;
else {
p[x] = y;
if (rank[x] == rank[y])
rank[y] = rank[y]+1;
}
}
}
Vamos resolver um problema com Union-Find.
Leiam agora o enunciado do UVa 1160.
momento de pausa...
Neste problema recebemos pares de "compostos" (que são inteiros) e que temos de processar.
Se usarmos a noção de conjuntos disjuntos, de início cada composto está isolado.
Quando chega o primeiro par, seja A+B, eles não pertencem ao mesmo conjunto mas podem ser unidos, dado que só se levantam problemas quando há N >2 compostos ao mesmo tempo.
Ao chegar o 2º par de compostos, como não há repetições, pelo menos um dos elementos é diferente de A ou B. E nesse sentido podemos voltar a uni-los. Por exemplo, vamos considerar que era o par A+C. Tudo bem, temos 2 pares com 3 compostos (não dá explosão!)
Mas no 3º par podemos ter problemas (ou não). Vejamos um exemplo de cada:
Se tivermos N-1 pares com N compostos diferentes, não podemos receber um par com dois desses compostos! Isto significa que apenas devemos recusar pares de compostos, quando ambos já pertencem ao conjunto, pois isso permitiria ter a tal combinação perigosa.
Ora esta condição pode ser implementada pelo FIND e pelo UNION da classe acima.
Basicamente, quando recebemos um novo par, perguntamos se ambos têm o mesmo representante. Se sim, recusamos (e actualizamos o número de recusas, que é o que queremos fazer output). Se não, então unimos os dois compostos no mesmo conjunto.
public class UVa_1160_X_Plosives {
public static void main(String[] args) throws IOException {
if (!new Object(){}.getClass().getName().contains("Main"))
try { // redirect System.in and System.out to in/out text files
System.setIn (new FileInputStream("data/uva1160.in.txt" ));
System.setOut(new PrintStream("data/uva1160.out.txt") );
} catch (Exception e) {}
///////////////////////////////////////////////////////////////
Reader1.init( System.in );
while (Reader1.hasNext()) {
Union_Find uf = new Union_Find(100000);
int refusals = 0;
do {
int x = Reader1.nextInt();
if (x==-1)
break;
int y = Reader1.nextInt();
if (uf.findSet(x) == uf.findSet(y)) // elements already on the same graph?
refusals++;
else // if not, join their graphs
uf.union(x,y);
} while (true);
System.out.println(refusals);
}
}
}
A classe Reader1 foi usada dado que o input é muito grande e o Scanner nestas situações demora muito tempo (vejam o guião sobre este assunto).
Eis o seu código:
class Reader1 {
static BufferedReader reader;
static StringTokenizer tokenizer;
static String next;
static boolean eof;
/** call this method to initialize reader for InputStream
* @throws IOException
*/
static void init(InputStream input) throws IOException {
reader = new BufferedReader( new InputStreamReader(input) );
tokenizer = new StringTokenizer("");
next = reader.readLine();
}
static boolean hasNext() {
return tokenizer.hasMoreTokens() || next!=null;
}
/** get next word
* @throws IOException
*/
static String next() throws IOException {
while ( ! tokenizer.hasMoreTokens() ) {
if (next == null) return null;
tokenizer = new StringTokenizer( next );
next = reader.readLine();
}
return tokenizer.nextToken();
}
static int nextInt() throws IOException {
return Integer.parseInt( next() );
}
}
Outros problemas UVa sugeridos: