Problem:-
Suppose that you are given no. 1 2,2 3,4 5 so here 1,2,3 will share same
path because of transitive relation between them and 4,5 will share other
route....and even if u are given no. like 1 2,3 4,1 4 then in this case
1,2,3,4 will share same path...so you will have to output total no of
path....i know it includes DFS.but still i am getting some error in
output...here is my code...
Input:-
1 2
3 4
1 4
6 7
Ouput:-2 ({1,2,3,4},{6,7})
/*
* To change this template, choose Tools | Templates
* and open the template in the editor.
*/
package chef;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.math.BigInteger;
import java.util.StringTokenizer;
/**
*
* @author Pardeep
*/
public class pathshare {
public static void main(String a[]) throws IOException
{
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
int t=Integer.parseInt(br.readLine());
for(int tes=0;tes<t;tes++){
StringTokenizer st=new StringTokenizer(br.readLine());
int n=Integer.parseInt(st.nextToken());
//String ar[]=new String[n+1];
int pre[]=new int[n+1];
long val[]=new long[n+1];
int sto[]=new int[n+1];
//int relst[]=new int[n+1];
boolean setflag=false;
boolean visit[]=new boolean[n+1];
for(int i=1;i<=n;i++)
{
//ar[i]=String.valueOf(i);
pre[i]=i;
visit[i]=false;
val[i]=1;
}
int rel=Integer.parseInt(st.nextToken());
// int stack[]=new
int[1000000];
int len=0;
while(rel>=1){
setflag=true;
st=new StringTokenizer(br.readLine());
int e1=Integer.parseInt(st.nextToken());
//stack[len++]=e1;
int e2=Integer.parseInt(st.nextToken());
if(!visit[e2]||!visit[e1])
{
int ch=pre[e2];int ch1=pre[e1];
if(pre[ch]!=pre[e2]&&visit[e2]){
pre[e2]=pre[ch];
ch=pre[e2];
}
if(pre[ch1]!=pre[e1]&&visit[e1]){
// System.out.println("upr");
pre[e1]=pre[ch1];
ch1=pre[e1];
}
//System.out.println("pr.."+pre[e1]+" "+pre[ch1]);
if(!visit[e1]&&visit[e2]){
pre[e1]=pre[e2];
val[pre[e1]]+=1;
visit[e1]=true;
}
else if(visit[e1]&&!visit[e2]){
pre[e2]=pre[e1];//System.out.println("checking...."); //1
2,3 4,1 4
val[pre[e2]]+=1;visit[e2]=true;
}
else if(!visit[e1]&&!visit[e2]){
pre[e2]=pre[e1];
val[pre[e2]]+=1;
visit[e2]=visit[e1]=true;
}
//visit[e2]=visit[e1]=true;
//System.out.println("ar: "+val[pre[e1]]+" "+pre[e1]);
//}
}
else if((visit[e2]&&visit[e1])&&pre[e2]!=pre[e1]){
val[pre[e1]]+=val[pre[e2]];
int ch=pre[e2];val[pre[e2]]=1;
while(ch!=pre[e1]){
pre[ch]=pre[e1];
ch=pre[ch];//System.out.println("lwr");
}
pre[e2]=pre[e1];
// System.out.println("visited.. "+val[pre[e1]]+" "+pre[e2]);
}
rel--;
}
BigInteger vallen= BigInteger.valueOf(1);
len=0;long mod=1000000007;
long valrel=0;boolean flag=false;long vf=0;boolean zero=false;
//for(int i=1;i<=n;i++) System.out.println(val[i]+" "+visit[i]);
for(int i=1;i<=n;i++){
if(val[i]==1&&!visit[i]){
//System.out.println("computing.... 1");
valrel++;zero=true;
}
else if(val[i]>1&&visit[i]&&vf!=0){
//System.out.println("computing..O");
vallen=vallen.multiply(BigInteger.valueOf(val[i])).mod(BigInteger.valueOf(mod));//System.out.println("m"+vallen);
//System.out.println("l.."+vallen);
valrel++;//len++;
flag=true;zero=true;
}
else if(val[i]>1&&visit[i]&&vf==0){
vf=val[i];valrel++;flag=true;
}
}
//if(!flag){ vallen=BigInteger.valueOf(1);vf=1;}
//if(!zero){vallen=BigInteger.valueOf(vf);}
// else
{vallen=vallen.multiply(BigInteger.valueOf(vf)).mod(BigInteger.valueOf(mod));}
//if(rel==0&&setflag==false){vf=0;vallen=vallen.multiply(BigInteger.ZERO);}
//System.out.println(bg);
System.out.println(valrel);
//System.out.println((valrel%mod)+" "+(vallen%mod));
}}
}
--
You received this message because you are subscribed to the Google Groups
"Google Code Jam" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
To post to this group, send email to [email protected].
To view this discussion on the web visit
https://groups.google.com/d/msg/google-code/-/TOYJDXEhq5UJ.
For more options, visit https://groups.google.com/groups/opt_out.
