URI PROBLEMA 1208 - As dinastias de São Petersburgo SOLUÇÃO EM C++

URI Online Judge | 1208

As dinastias de São Petersburgo

Por Gabriel R. de C. Peixoto  Brasil

Timelimit: 2

São Petersburgo foi fundada no dia 27 de maio de 1703 pelo czar Pedro, o Grande, e foi capital imperial da Rússia por um período curto logo após (de 1713 a 1728) e depois por quase dois séculos, de 1732 a 1918. Neste último período o trono imperial russo acabou sendo ocupado por diversos imperadores, muitas vezes de linhas de dinastia diferentes. Na tradição imperial russa chama-se de текущий (lê-se текущий 1*) uma sequência de descendentes dentro de uma dinastia, ou seja, um elemento, seu filho, seu neto, e assim por diante. A determinação destas текущий é fundamental quando se deseja determinar o sucessor do atual imperador, uma vez que o próximo imperador é o elemento vivo de uma текущий que esteja mais próxima do atual imperador.

É claro que uma árvore genealógica pode ser dividida em текущий de várias formas diferentes. O interessante é encontrar uma partição que minimize o número de текущий necessário para cobrir todos os elementos da dinastia.

Sua tarefa neste problema é determinar, dada a árvore genealógica da família imperial russa, o menor número de текущий que particionam toda a família imperial, isso é, todos os imperadores tem que pertencer à exatamente uma текущий e essas têm que ser o menor número possível.

Entrada

A entrada é composta por diversas instâncias e termina com final de arquivo (EOF). A primeira linha de cada instância contém dois inteiros N (1 ≤ N ≤ 1000) e (M 0 ≤ M ≤ 10000) representando, respectivamente, a quantidade de imperadores e o número de relações de filiação naquela instância. Os imperadores são identificados por números de 1 à N. Cada uma das próximas M linhas contém dois inteiros Pi (1 ≤ Pi < Fi) e Fi (Pi < Fi ≤ N), indicando que Pi é pai de Fi. Uma particularidade da da árvore genealógica dada é que em caso de dúvidas de paternidade, todos os possíveis pais eram indicados, ou seja, uma pessoa pode ter qualquer número de pais.

Saída

Para cada instância imprima uma linha contendo um único número inteiro, que é o número mínimo de текущий necessários para particionar todos os imperadores daquela instância.

#include <cstdio>

#include <vector>

#define MAXN 2001

using namespace std;

int n,m;

vector<int> grafo[MAXN],vis,match;

int augmenting_path(int l){

if(vis[l]) return 0;

vis[l] = 1;

for(int i=0;i<grafo[l].size();i++){

int r = grafo[l][i];

if(match[r] == -1 || augmenting_path(match[r])){

match[r] = l;

return 1;

}

} 

return 0;

}

int main(){

while(scanf("%d %d",&n,&m) != EOF){

for(int i=1;i<=n;i++){

grafo[i].clear();

}

for(int i=1;i<=m;i++){

int u,v;

scanf("%d %d",&u,&v);

grafo[u].push_back(v+n);

}

int resp = n;

match.assign(2*n+2,-1);

for(int i=1;i<=n;i++){

vis.assign(n+2,0);

resp -= augmenting_path(i);

}

printf("%d\n",resp);

}

return 0;

}