793 - Network Connections

[Jan]

What is the output for the following input set... Can anyone tell me..

Code: Select all

1 

5
c 1 3
c 3 4
c 4 5
q 1 2
q 3 4
q 1 5
q 3 5

Thanks in advance.

[Jan]

Riyad, I think this is a multiple input problem. And for this, u have to initialize p[] for every input set. Otherwise for same input set more than once u will get different answers.

And another thing, in your code I found...

Code: Select all

m=p[x]; 
n=p[y];    

p[y]=n;  //No meaning, I think it should be p[x]=n

Hope it works...

[PG]

Is there a better way to solve this question?

Thanks for your advise .

Code: Select all

#include<iostream>
using namespace std;
///////////////////////////////////////////////////////////////////////////////
typedef struct _set
{
  int v,t;
}PG;
PG s[1001];
void makeset(PG* s,int smax) 
{
  for(int i=1;i<=smax;i++){s[i].v=i;s[i].t=i;}
}
int find(PG *s,int a)  
{
  while(s[a].t!=a)a=s[a].t;
  return a;
}
void merge(PG *s,int a,int b)  
{
  a=find(s,a);b=find(s,b);
  if(a<b)s[b].t=a;
  else s[a].t=b;
}
bool same(PG *s,int a,int b)
{
  if(find(s,a)==find(s,b))return true;
  else return false;
}
void print_s(PG *s,int smax)
{
  for(int i=1;i<=smax;i++)cout<<s[i].v<<" "<<s[i].t<<endl;
}
///////////////////////////////////////////////////////////////////////////////
int main()
{
  int qmax,cmax,y,n;
  int t1,t2;

  char ch;
  cin>>qmax;
  for(int qi=1;qi<=qmax;qi++)
  {
      y=n=0;
      cin>>cmax;
      makeset(s,cmax);
      cin.get();

      while(1)
      {
          ch=cin.peek();
          if(ch=='\n')break;
          cin.get();
          cin>>t1>>t2;
          if(ch=='c')
              merge(s,t1,t2);
          if(ch=='q')
          {
              if(same(s,t1,t2))y++;
              else n++;
          }
          cin.get();


      }
      cout<<y<<","<<n<<endl<<endl;
  }
}

[Wei-Ming Chen]

3,1

[Wei-Ming Chen]

I thought my code is fast, but TLE.....

Can someone tell me why?





No it's slow

DO NOT use DFS in this problem

[IRA]

Why WA!?
I can't find my bug...
Please help me to find the bug.
Thanks in advance!

Code: Select all

I have got AC!

[Jan]

Thanks, got Accepted...

[Moha]

I use same method(disjoint-set) and got it. maybe you should check before merging that if two sets are equal or not

[asif_rahman0]

isnt this algo enogh for this is proble??
plz help me

Code: Select all

removed

thnx for helping

[Moha]

You didn't test the connection before make a connection. your program may be create a cycle.

[asif_rahman0]

can someone tell me about multiple I/O??
i m getting TLE because of this thing. so plz reply me back so that i can get accepted.

Code: Select all

removed

[asif_rahman0]

still no reply:(

[mamun]

still no reply:(

Only about 2 hours have passed between your 2 posts. Think, you are too optimistic.

can someone tell me about multiple I/O??

Read this - http://acm.uva.es/problemset/minput.html
AFAIK now all problem descriptions are described such. Read the same problem statement at http://acm.uva.es/p/v7/793.html

i m getting TLE because of this thing.

I don't think so.

[asif_rahman0]

mamun vai,
i submitted this problem many times. but when i read input with EOF then i got WA. and If not then TLE.

i m sure that i wont get TLE at all if the input file isnt too big.
my algo is good enough.
ok
so plz reply me how to get rid of from TLE??

[serur]

Hey man,
I had problems with EOF too, but this worked:

Code: Select all

scanf("%d\n",&T);
	while(T--){
		scanf("%d\n",&n);
		rank=malloc((n+1)*sizeof *rank);
		p=malloc((n+1)*sizeof *p);
		for(i=1;i<=n;i++)
			make_set(i);
		n1=n2=0;
		while(gets(s)!=NULL && sscanf(s,"%c %d %d",&ch,&i,&j)==3){
		/*blah-blah/*
                            }feof(stdin))
                                           break;						
		}

You use union-find?