## 793 - Network Connections

Moderator: Board moderators

raj
Learning poster
Posts: 78
Joined: Fri Feb 15, 2013 5:39 pm

### Re: 793 - Network Connections

Need Help I dont know Why its """Run Time Error"""

Code: Select all

``````import java.io.*;
import java.util.*;
class UnionFind{
int [] rank;
int [] Parent;
public UnionFind(int size){
rank = new int[size];
Parent = new int[size];
for(int i = 0;i<Parent.length;i++){
Parent[i] = i;
}
}
public void MergeSets(int x,int y){
int PX = FindSet(x);
int PY = FindSet(y);
if (rank[PX] > rank[PY]) Parent[PY] = PX; // means py er parent ekhon px
else Parent[PX] = PY;
if (rank[PX] == rank[PY]) rank[PY] = rank[PY] + 1; // 2 ta rank soman thaka means ekta tree er size barano
}
public int FindSet(int x){
if (x != Parent[x]) Parent[x] = FindSet(Parent[x]);
return Parent[x];
}

public boolean isSameSet(int x,int y){
return FindSet(x) == FindSet(y);
}
}
public class Main{
public static void main(String [] args)throws IOException{
PrintWriter z = new PrintWriter(System.out);
while(T-->0){
UnionFind a = new UnionFind(number);
int success = 0,unsuccess = 0;
String line;
StringTokenizer s = new StringTokenizer(line);
String cheq = s.nextToken();
int n = Integer.valueOf(s.nextToken());
int m = Integer.valueOf(s.nextToken());
boolean l = true;
//int success = 0,unsuccess = 0;
if(cheq.equals("c")){
a.MergeSets(n, m);
}
else{
l = a.isSameSet(n,m);
if(l) success++;
else unsuccess++;
}
}
z.println(success+","+unsuccess);
if(T!=0)z.println();
}
z.flush();
}
}

``````

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 793 - Network Connections

Try input:

Code: Select all

``````1

2
c 1 2
q 1 2``````
Check input and AC output for thousands of problems on uDebug!

lukai
New poster
Posts: 25
Joined: Wed Dec 05, 2012 8:11 pm

### 793 - Network Connections

I tried various test cases, They all pass. I don't know why I am getting WA?

Code: Select all

``````#include<cstdio>
#include<sstream>
#include<cstdlib>
#include<cctype>
#include<cmath>
#include<algorithm>
#include<set>
#include<queue>
#include<stack>
#include<list>
#include<iostream>
#include<fstream>
#include<numeric>
#include<string>
#include<vector>
#include<cstring>
#include<map>
#include<iterator>
using namespace std;

typedef vector<int>vi;

vi pset(100000),setSize(100000);
void initSet(int N)
{
setSize.assign(N,1);
pset.assign(N,0);
for(int i=0;i<N;i++)
{
pset[i]=i;
}
}

int findSet(int i)
{
return (pset[i]==i)?i:(pset[i]=findSet(pset[i]));
}

bool isSameSet(int i,int j)
{
return findSet(i)==findSet(j);
}

void unionSet(int i,int j)
{
if(!isSameSet(i, j))
{
setSize[findSet(j)]+=setSize[findSet(i)];
pset[findSet(i)]=findSet(j);
}
}

int main()
{
//freopen("input.txt","r",stdin);
//freopen("output.txt","w",stdout);

int cases,number_of_telephone,success,failure,qcounter;
cin>>cases;
getchar();
string connections;
while(cases--)
{
success=failure=0;
cin>>number_of_telephone;
getchar();
initSet(number_of_telephone);
while(getline(cin, connections)&&connections.size())
{
if(connections[0]=='c')
{
unionSet(connections[2]-'0',connections[4]-'0');
}
if(connections[0]=='q')
{
if(isSameSet(connections[2]-'0',connections[4]-'0'))
{
success++;
}
else
{
failure++;
}
}
}
cout<<success<<","<<failure<<endl;
if(cases>0)
{
cout<<endl;
}
pset.clear();
setSize.clear();
}

return 0;
}

``````

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 793 - Network Connections

Try input:

Code: Select all

``````1

50
c 1 30
q 3 1
``````
Check input and AC output for thousands of problems on uDebug!

lukai
New poster
Posts: 25
Joined: Wed Dec 05, 2012 8:11 pm

### Re: 793 - Network Connections

Thanks Brianfry, AC . Such a stupid mistake.

Martin91
New poster
Posts: 2
Joined: Mon Nov 18, 2013 11:20 pm

### Re: 793 - Network Connections

Hello.

Here's my code:

Code: Select all

``````#include <iostream>
#include <vector>
#include <cstring>
#include <cstdio>
#include <string>

using namespace std;

#define REP(i,a,b) for(int i =int(a);i<int(b);i++)

vector<int> pset(100);
vector<int> rset(100);
void initSet(int _size) {pset.resize(_size);rset.assign(_size,0); REP(i,0,_size) pset[i]=i;}
int findSet(int i) {return (pset[i]==i) ? i: (pset[i]=findSet(pset[i])); }
bool isSameSet(int i, int j) {return findSet(i)==findSet(j);}
void unionSet(int i, int j) {
if(i==j) return;
if(rset[i]>rset[j])
pset[j]=i;
else {
pset[i]=j;
if(rset[i]==rset[j])
rset[j]++;
}
}

int main()
{
int T,st,rac1,rac2,prav,narobe;
char cq;
string niz;

//freopen("in.txt","r",stdin);

scanf("%d",&T);

REP(i,0,T){
scanf("\n%d\n",&st);
initSet(st);
prav=0;
narobe=0;
while(true) {
if(!getline(cin,niz) || niz.empty()) break;
sscanf(niz.c_str(),"%c %d %d",&cq,&rac1,&rac2);
int i = findSet(rac1);
int j = findSet(rac2);
if(cq=='c')
unionSet(i,j);
else if (cq=='q') {
if(isSameSet(i,j))
prav++;
else
narobe++;
}
}

if(i!=0)
printf("\n");
printf("%d,%d\n",prav,narobe);
}
return 0;
}
``````

Martin91
New poster
Posts: 2
Joined: Mon Nov 18, 2013 11:20 pm

### Re: 793 - Network Connections

Found the error. Thanks anyway

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 793 - Network Connections

That is AC code
Check input and AC output for thousands of problems on uDebug!

triplemzim
New poster
Posts: 48
Joined: Sat Apr 06, 2013 6:02 pm

### Re: 793 - Network Connections

There is no blank line after the last dataset. So be careful about EOF to avoid TLE.

dibery
Learning poster
Posts: 76
Joined: Sat Feb 23, 2013 4:16 pm
Location: Taiwan, Taipei
Contact:

### Re: 793 - Network Connections

Another test case.

input:

Code: Select all

``````10

10
q 5 1
c 4 9
c 4 10
c 9 5
q 5 8
c 8 5
q 1 8
q 1 9
c 3 9
c 1 7
c 1 9
c 1 4
q 10 1
q 7 8
q 4 10
q 10 8
q 8 5
q 8 9
q 6 5
q 5 7

10
c 5 4
c 10 10
c 1 7
c 10 1
q 9 1
q 7 7
c 3 1
q 2 7
c 7 3
c 5 4
q 1 2
c 10 5
c 8 9
c 8 4
c 8 5
c 6 3
q 7 9
c 3 6
c 8 10
c 1 10

10
c 4 7
q 9 7
c 9 9
q 2 2
c 8 3
c 2 5
c 1 2
c 6 2
q 6 7
q 7 8
q 3 4
q 2 9
q 2 6
c 3 9
q 8 2
c 2 1
c 5 6
c 9 9
q 5 5
q 3 9

10
q 6 4
c 6 4
q 3 4
c 4 4
q 5 5
c 5 5
c 3 6
c 1 2
q 7 1
q 8 9
c 3 5
q 8 3
c 3 5
q 6 7
q 10 4
q 6 10
q 3 9
c 4 3
c 6 4
q 6 10

10
q 10 10
c 3 5
c 7 6
q 5 3
c 9 1
q 10 5
c 1 3
q 3 6
q 8 9
c 8 10
c 9 1
c 4 3
c 1 3
c 3 4
c 3 3
c 7 10
c 9 3
c 6 10
q 4 10
c 6 8

10
q 8 2
c 10 3
c 4 8
c 8 1
c 2 6
c 1 4
c 5 1
c 4 10
q 6 1
c 5 1
q 6 1
q 8 7
c 7 8
q 7 9
c 5 2
q 8 9
q 10 2
q 9 7
c 1 6
c 1 1

10
c 1 10
q 9 9
c 8 7
c 8 8
c 1 9
q 9 10
c 2 4
c 9 1
c 6 5
q 6 6
q 8 9
c 6 10
q 2 1
q 1 8
q 1 3
c 1 5
q 4 3
q 6 3
q 2 10
c 7 8

10
q 8 8
c 7 10
q 9 1
c 6 10
c 1 8
c 7 8
c 1 7
q 3 8
q 5 10
q 4 6
c 3 10
q 2 10
q 3 8
q 4 8
q 1 9
q 10 1
q 7 2
c 6 1
c 5 6
q 3 4

10
q 4 10
c 5 4
c 2 6
q 10 6
q 10 4
q 10 4
q 4 10
c 4 7
c 1 8
c 6 3
q 6 3
c 1 5
q 6 10
c 1 6
c 7 6
q 10 9
c 10 1
c 6 7
c 3 10
c 7 9

10
q 9 1
q 5 5
c 4 6
c 1 9
c 7 2
c 7 5
q 7 8
c 5 5
c 6 6
c 4 2
c 6 1
c 3 9
q 8 7
c 8 10
c 10 3
c 6 7
c 5 8
c 10 10
q 7 7
c 8 8``````
output:

Code: Select all

``````7,5

2,3

4,6

1,10

2,4

1,7

3,7

3,9

1,7

2,3
``````
Life shouldn't be null.

Chuckrute
New poster
Posts: 5
Joined: Thu Apr 10, 2014 12:32 am

### Re: 793 - Network Connections

Can someone tell me why i got WA?

Code: Select all

``````Got AC! Code removed!

}``````

PS: I tested every test case in this post.

Edit: Stupid mistake!
Last edited by Chuckrute on Thu Apr 10, 2014 2:02 pm, edited 1 time in total.

lbv
Experienced poster
Posts: 128
Joined: Tue Nov 29, 2011 8:40 am

### Re: 793 - Network Connections

Chuckrute wrote:Can someone tell me why i got WA?
The output must end in a newline (but not a blank line).

Chuckrute
New poster
Posts: 5
Joined: Thu Apr 10, 2014 12:32 am

### Re: 793 - Network Connections

lbv wrote:
Chuckrute wrote:Can someone tell me why i got WA?
The output must end in a newline (but not a blank line).
Thanks!

apcastelein
New poster
Posts: 15
Joined: Wed Jul 23, 2014 12:57 am

### Re: 793 - Network Connections

Hello
I've tried several test cases on mine. I'm not sure why I'm getting WA

Code: Select all

``````I got AC Thanks :)
``````
I've noticed reading through this thread that the input output is of the format

Code: Select all

``````#testcases

#computers
cmd1
cmd2
cmd3
...

#computers
cmd1
cmd2
...

``````
My code isn't made to handle this but I read through the problem again and I don't see it saying the code needs to handle multiple test cases anywhere. Did I misunderstand something?
Last edited by apcastelein on Mon Sep 08, 2014 11:01 pm, edited 1 time in total.

lighted
Guru
Posts: 587
Joined: Wed Jun 11, 2014 9:56 pm
Location: Kyrgyzstan, Bishkek

### Re: 793 - Network Connections

Yes this is problem with multiple input.
Old link is not working http://acm.uva.es/problemset/minput.html
See http://www.algorithmist.com/index.php/UVa_793
A person who sees the good in things has good thoughts. And he who has good thoughts receives pleasure from life... Bediuzzaman