//Description: Component.java is used to identify network components for a given list of network nodes. 
//It is able to identify not only the network components for the whole network but also can identify 
//network components for a subset of network nodes.
//Author: Dr. Qinghua Cui, Department of Biomedical Informatics, PKU Health Science Center, cuiqinghua@hsc.pku.edu.cn
//website of Cui lab: http://www.cuilab.cn
//Date: 2010-09-18


import java.io.*;
import java.lang.*;
import java.util.regex.*;
import java.util.Arrays;
 

 
public class Component
{
	private static String REGEX="\\s{1,}";
	private static String line;
	private static int nodnum=306;/////////the number of nodes of the network
	private static int subnodnum=306;////////the number of the subset of nodes
	private static int adjMatrix [][]=new int [nodnum][nodnum];
	private static int nodes []=new int [nodnum];
	private static int subnode []=new int [subnodnum];
	private static int component []=new int [subnodnum];
	
	private static int d []=new int [nodnum];
	private static int T []=new int [nodnum];
	private static int S []=new int [nodnum];
	private static int Q []=new int [nodnum];
	private static int startpoint;
	private static int u;

 
	private static Pattern pattern;

	public void inite()
	{
		for(int i=0;i<nodnum;i++)
		{
			
			d[i]=Integer.MAX_VALUE;
			T[i]=-1;
			nodes[i]=i;
			S[i]=0;
			Q[i]=0;
			
		}
		d[startpoint-1]=0;
		Q[startpoint-1]=1;
		
	}

	public void step1()
	{
		int distance=Integer.MAX_VALUE;
		int index=0;
		for(int i=0;i<nodnum;i++)
		{
			if(Q[i]==1 && d[i]<distance)
			{
				distance=d[i];
				index=i;
			}
		}
		Q[index]=0;
		u=index;
		S[u]=1;
	}

	public void step2()
	{
		for(int i=0;i<nodnum;i++)
		{
			if(adjMatrix[u][i]>0 && S[i]==0)
			{
				if(d[i]>d[u]+adjMatrix[u][i])
				{
					d[i]=d[u]+adjMatrix[u][i];
					T[i]=u;
					Q[i]=1;
				}
			}
		}
	}

	public int sumQ()
	{
		int sumq=0;
		for(int i=0;i<nodnum;i++)
		{
			sumq+=Q[i];
		}
		return sumq;
	}


	public static void main(String [] args)
 	{
  		//String line="";
		BufferedReader in=null;
		PrintWriter out=null;

		for(int i=0;i<nodnum;i++)
		{
			for(int j=0;j<nodnum;j++)
			{
				adjMatrix[i][j]=0;
			}
		}



 		try
		{
			in=new BufferedReader(new FileReader("node2.txt"));///the subset of nodes
   
		}
		catch(FileNotFoundException fufe)
		{
			fufe.printStackTrace();
		}		
		catch(IOException ioe)
		{
		ioe.printStackTrace();
		}
 
 		try
  		{
			pattern=Pattern.compile("\\s{1,}");
      
			line=in.readLine();
			int m=0;
			while(line!=null)
   		{
    				String [] items1=pattern.split(line);
    				subnode[m]=Integer.parseInt(items1[0]);
						m++;
    				line=in.readLine();
      
    
   		}
   			in.close();
  		}
  		catch(IOException ioe)
  		{
   			ioe.printStackTrace();
  		}

 		try
		{
			in=new BufferedReader(new FileReader("newlink.txt"));///the network links
   
		}
		catch(FileNotFoundException fufe)
		{
			fufe.printStackTrace();
		}		
		catch(IOException ioe)
		{
		ioe.printStackTrace();
		}
 
 		try
  		{
			pattern=Pattern.compile(REGEX);
      
			line=in.readLine();
			while(line!=null)
   		{
    		String [] items1=pattern.split(line);

				int from=Integer.parseInt(items1[0]);
				int to=Integer.parseInt(items1[1]);

				int k1=Arrays.binarySearch(subnode,from);
				int k2=Arrays.binarySearch(subnode,to);
				
				if(k1>=0 && k2>=0)
				{
    					adjMatrix[from-1][to-1]=1;
    					adjMatrix[to-1][from-1]=1;
				}

    				line=in.readLine();
      
    
   			}
   			in.close();
  		}
  		catch(IOException ioe)
  		{
   			ioe.printStackTrace();
  		}

		int starts []=new int [subnodnum];
		int ends []=new int [subnodnum];

		for(int i=0;i<subnodnum;i++)
		{
			starts[i]=subnode[i];
			ends[i]=subnode[i];
		}
		
		
		
		
		try
		{
			out=new PrintWriter(new FileWriter("component.txt"));///the output of network component
		}
		catch(FileNotFoundException fufe)
		{
			fufe.printStackTrace();
		}		
		catch(IOException ioe)
		{
		ioe.printStackTrace();
		}


		for(int i=0;i<subnodnum;i++)
		{
			component[i]=0;
		}
		
		int m=0;
		for(int i=0;i<subnodnum;i++)
		{
			startpoint=starts[i];
			Component cp=new Component();
			cp.inite();
			while(cp.sumQ()>0)
			{
				cp.step1();
				cp.step2();
			}
			
			if(component[i]==0)
			{
				m++;
				component[i]=m;
			}


			for(int j=0;j<subnodnum;j++)
			{

				int endpoint=ends[j];
				int numnode_path=0;

				if(adjMatrix[startpoint-1][endpoint-1]==1)
				{
					component[j]=component[i];
				}

				if(T[endpoint-1]==-1  || ends[j]==starts[i])
				{
					continue;
				}

				while(T[endpoint-1]!=-1)
				{
					numnode_path++;
					endpoint=T[endpoint-1]+1;
				}

				endpoint=ends[j];
				int path []=new int [numnode_path];

				while(T[endpoint-1]!=-1)
				{
					numnode_path--;
					path[numnode_path]=endpoint;
					endpoint=T[endpoint-1]+1;
				}


				if(path.length>1 && component[j]==0)
				{
					component[j]=m;
				}



			}

			
		}
			

		for(int i=0;i<subnodnum;i++)
		{
			out.write(component[i]+"\n");
		}
		
		out.close();

 
  
	}
}
