10608 - Friends

All about problems in Volume 106. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

notquitethecoda
New poster
Posts: 1
Joined: Sat Sep 17, 2016 7:15 pm

Re: 10608 - Friends Getting RE

Post by notquitethecoda » Sat Sep 17, 2016 7:23 pm

It's been a while and I still can't figure out what went wrong...
The code runs and got identical results as uDebug on my machine but it got RE on uva OJ
Can anyone please help me on finding what's wrong with my code?? Thanks~~

Code: Select all


import java.io.IOException;
import java.util.StringTokenizer;

class Main {
	
	static final int MAX = 1000;
	
	static String ReadLn (int maxLg)  // utility function to read from stdin
    {
        byte lin[] = new byte [maxLg];
        int lg = 0, car = -1;
        String line = "";

        try
        {
            while (lg < maxLg)
            {
                car = System.in.read();
                if ((car < 0) || (car == '\n')) break;
                lin [lg++] += car;
            }
        }
        catch (IOException e)
        {
            return (null);
        }

        if ((car < 0) && (lg == 0)) return (null);  // eof
        return (new String (lin, 0, lg));
    }
	

	private int[] friendsCircle;
	private int[] friendsCount;
	private int maxFriendsCount;
	
	
	public void setCityStatus(int pplCount){
		int size = pplCount+1;
		this.friendsCircle = new int[size];
		this.friendsCount = new int[size];
		this.maxFriendsCount = 0;
		for(int i=0; i<size; i++){
			this.friendsCircle[i] = -1;
			this.friendsCount[i] = 1;

		}
	}
	
	public void readStatement(int friend1, int friend2){
		int friendHead1 = getFriendHead(friend1);
		int friendHead2 = getFriendHead(friend2);
		if(this.maxFriendsCount == 0){
			this.maxFriendsCount = 1;
		}
		if(friendHead1 != friendHead2){
			addFriend(friendHead1, friendHead2);
		}
	}
	
	public void addFriend(int friend1, int friend2){
		
		int currentFriendsCount = this.friendsCount[friend1] += this.friendsCount[friend2];
		if(currentFriendsCount > this.maxFriendsCount){
			this.maxFriendsCount = currentFriendsCount;
		}
		this.friendsCount[friend1] = currentFriendsCount;
		this.friendsCircle[friend2] = friend1;
		
	}
	
	public int getFriendHead(int friend){
		if(this.friendsCircle[friend] == -1){
			return friend;
		}else{
			this.friendsCircle[friend] = getFriendHead(this.friendsCircle[friend]);
			return this.friendsCircle[friend]; 
		}
	}
	
	public int getMaxFriends(){
		return this.maxFriendsCount;
	}
	
	public static StringTokenizer getInputData(){
		StringTokenizer data = null;
		String input;
		while((input = Main.ReadLn(MAX)) != null){
			data = new StringTokenizer(input.trim());
			break;
		}
		return data;
	}

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Main problemSovler = new Main();
		StringTokenizer idata = null;
		String input;
		int caseCount;
		int pplCount;
		int statementCount;
		int friend1, friend2;
		
		while((input = Main.ReadLn(MAX)) != null){
			
			idata = new StringTokenizer(input.trim());
			if(!idata.hasMoreTokens()){
				idata = getInputData();
			}
			caseCount = Integer.parseInt(idata.nextToken());
			while(caseCount > 0){
				if(!idata.hasMoreTokens()){
					idata = getInputData();
				}
				pplCount = Integer.parseInt(idata.nextToken());
				if(!idata.hasMoreTokens()){
					idata = getInputData();
				}
				statementCount = Integer.parseInt(idata.nextToken());
				problemSovler.setCityStatus(pplCount);
				while(statementCount > 0){
					if(!idata.hasMoreTokens()){
						idata = getInputData();
					}
					friend1 = Integer.parseInt(idata.nextToken());
					if(!idata.hasMoreTokens()){
						idata = getInputData();
					}
					friend2 = Integer.parseInt(idata.nextToken());
					
					problemSovler.readStatement(friend1, friend2);
					statementCount--;
					if(statementCount == 0){
						break;
					}
				}
				System.out.println(problemSovler.getMaxFriends());
				caseCount--;
				if(caseCount == 0){
					break;
				}
				
			}
			
		}

	}

}


Post Reply

Return to “Volume 106 (10600-10699)”