CodinGame JULY 2013 #1

CodinGame-JULY2013-1-Solution.java

/**
La citation "Des nains sur des épaules de géants" se réfère à l'importance pour tout homme de s'appuyer sur les travaux de ses prédécesseurs.
 
À la lecture des textes, on ne glane qu'une petite partie de cette dépendance : telle personne a influencé telle autre personne. On apprendra par la suite que cette seconde personne en a, à son tour, influencé une troisième, et ainsi de suite. C'est cette chaîne d'influence qui nous intéresse dans cet exercice, et plus précisément, il s'agit de trouver la longueur de la plus grande de ces chaînes.
 
On choisit de représenter chaque personne par un nombre entier distinct. Si la personne 1 a influencé les personnes 2 et 3, et que 3 a influencé 4, alors il existe une succession de pensée entre 1, 3 et 4. C'est la plus longue succession existant dans ce cas, et le résultat attendu sera 3 car elle implique 3 personnes.
 
Si on complète cet exemple en apprenant que 2 a également influencé 4 et 5, la plus longue succession reste de longueur 3, mais il en existe désormais plusieurs.
 
Si on ajoute que 10 a influencé 11, le résultat reste 3. Mais dès que l'on apprend que 10 a également influencé 1 et 3, alors le résultat devient 4, car il existe alors par exemple la succession 10, 1, 2, 5 comportant 4 personnes.

Il faut du temps pour qu'une pensée en influence d'autres. Aussi, on supposera qu'il n'est pas possible d'avoir d'influence mutuelle entre les personnes. Autrement dit, si A influence B (même indirectement via d'autres personnes), alors B n'influencera pas A (même indirectement). Il est également impossible de s'influencer soi-même.
 
ENTRÉE :
Ligne 1 : le nombre N de relations d'influence.
N lignes suivantes : une relation d'influence entre deux personnes, de la forme X (espace) Y, indiquant que X influence Y. Les relations d'influence sont listées dans un ordre quelconque.
 
SORTIE :
Le nombre de personnes impliquées dans la plus longue succession d'influences.
 
CONTRAINTES :
0 < N < 10000
0 < X,Y < 10000

EXEMPLES :
Entrée
3
1 2
1 3
3 4

Sortie
3
 
 
Entrée
8
1 2
1 3
3 4
2 4
2 5
10 11
10 1
10 3

Sortie
4
 
 
Entrée
4
2 3
8 9
1 2
6 3

Sortie
3

*/
/**
 * */
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Set;

/**
 * Solution
 * */
public class Solution {
    private static Solution solution=new Solution();
  private static Map<Integer,Person> mapPersons=Collections.synchronizedMap(new HashMap<Integer,Person>());
	
	/**
	 * Person
	 * */
	private class Person{
		Integer id;
		Integer maxInfluencers=0;
		Set<Integer> setPred=Collections.synchronizedSet(new HashSet<Integer>()); // Predecessors (Influencers)
		Set<Integer> setSucc=Collections.synchronizedSet(new HashSet<Integer>()); // Successors
		
		public Person(Integer id){
			this.id=id;
		}
	}
	
	/**
	 * newPerson
	 * Creates new Person and add it to the Person's map.
	 * 
	 * @param id ID for new Person
	 * @return Newly created Person (added in map)
	 * */
	private Person newPerson(Integer id){ return new Person(id); }
	
	/**
	 * getPerson
	 * Retrieves Person with specified ID, or creates new one if it does not exist. 
	 * 
	 * @param id ID of Person to retrieve. 
	 * @return Person
	 * */
	private Person getPerson(Integer id){
		if(!mapPersons.containsKey(id))			
			mapPersons.put(id, solution.newPerson(id)); // Creates new Person if it does not exist.
		return mapPersons.get(id);
	}
	
	/**
	 * @param args
	 */
	public static void main(String[] args) {

		// Standard INPUT
    	BufferedReader reader =new BufferedReader(new InputStreamReader(System.in)); 
    	
    	try {
    		
    		/**/
    		Integer n=Integer.valueOf(reader.readLine().trim());
    		for(int i=0;i!=n;i++){
    			String[] p=reader.readLine().trim().split(" ", 2);
    			Person influencer=solution.getPerson(Integer.valueOf(p[0].trim()));
    			Person influenced=solution.getPerson(Integer.valueOf(p[1].trim()));    			
    			influencer.setSucc.add(influenced.id);
    			influenced.setPred.add(influencer.id);
    		}
    		
    		/* Explores Influence Tree. */
    		List<Person> listPersons=Collections.synchronizedList(new ArrayList<Person>());
    		for(Person p:mapPersons.values()) // Retrieves Root(s).
    			if(p.setPred.isEmpty())
    				listPersons.add(p);
    		while(!listPersons.isEmpty()){
    			Person p=listPersons.remove(0); // Influencer. 
    			for(Integer ip:p.setSucc){
    				Person inPerson=solution.getPerson(ip); // Influenced Person.
    				inPerson.maxInfluencers=Math.max(inPerson.maxInfluencers,p.maxInfluencers+1);
    				listPersons.add(inPerson);
    			}
    		}
			
    		/* Extracts Result. */
    		Integer nResult=0;
    		for(Person p:mapPersons.values())
    			nResult=Math.max(nResult, p.maxInfluencers);
    		System.out.println(nResult+1);
    		
			reader.close();
						
		} catch (IOException e) {
			
			e.printStackTrace();
		} 
	}
}