793 - Network Connections

[serur]

I see you use DFS, but it's better to switch to Union-find, really.

[mamun]

As far as your input is concerned you'll not get TLE but WA. Test this case

Code: Select all

1

10
c 2 5
q 2 5

There is no specification about the input range. So no idea how many vertices you have to deal with. Maybe even large enough to fit in your 10 sized s1 and s2 arrays! Calling DFS so many times will cause TLE.

Use dijsoint sets.

[asif_rahman0]

above input is now ok. and also others input/output. Any more I/O!!!
now i m getting WA..... so sad!!!
plz help

Code: Select all

removed


[mamun]

A very straightforward input to show your error

Code: Select all

2

2
c 1 2
q 1 2

3
c 1 3
q 1 2

[asif_rahman0]

thnx mamun vai

[898989]

Salamo Aleko.
Sorry i do not like reading codes...

But this is a good advice....
In many contests you may face diffrent problems like this, trying every time to make good and fast algorithm is not some thing good.
There is a algorithm called "Union Find operation with path compression"
This is the fastest know lgorithm for Union Find operation. Moreover it is to simple. You can find the full source code in this book
"Introduction to algorithms"
You can solve with it efficiently the next problems
"793 10583 10685 10608 615"

[Darko]

I've used my faulty union-find to solve a few problems, but this one made me realize that it doesn't work quite the way I thought it would.

Here's a case on which my implementation is failing:

Code: Select all

1

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


Output should be

Code: Select all

2,0

P.S. Instead of C&P I retyped it and that caused its faultiness, it was ok all along.

[Wei-Ming Chen]

You are right

I use the method and got AC on 793 and 10583

Thanks your help

[f.eliel]

My code worked fine for every test case i found here, but i still get WA.
Can someone help me?

Here is my code:

Code: Select all

#include <stdio.h>

#define max 1000

int m[max][max], d[max];
int fila[max], inicio, fim;
int suc, unsuc;

void adiciona(int a, int b) {
   int i;
   for (i = 1; i <= m[a][0]; i++)
      if (m[a][i] == b) break;
   if (i = m[a][0]+1) {
      m[a][++m[a][0]] = b;
      m[b][++m[b][0]] = a;
   }
}

void colocanafila(int n) {
     fila[fim++] = n;
     if (fim > (max-1)) fim = 0;
}

int retiradafila() {
    int ret;
    if (inicio == fim) ret = -1;
    else ret = fila[inicio++];
    if (inicio > (max-1)) inicio = 0;
    return ret;
}

void bfs(int a, int b) {
   int i, w;
     
   memset(d, -1, sizeof(d));
   d[a] = 1;
   inicio = fim = 0;
   w = a;
   while (w != -1) {
      for(i = 1; i <= m[w][0]; i++) {
         if (d[m[w][i]] == -1) {
            if (m[w][i] == b) {
               suc++;
               w = 0;
               break;
            }
            else {
               d[m[w][i]] = 1;
               colocanafila(m[w][i]);
            }
         }
      }
      if (!w) break;
      w = retiradafila();           
   }
   if (w == -1) unsuc++;
}


int main()
{
   int t, n, q, w, first=1;
   int ci, cj;
   char tipo[2];
   
   scanf("%d", &t);
   while (t) {
      if (first) first = 0;
      else printf("\n");
      t--;
      memset(m, 0, sizeof(m));
      suc = unsuc = 0;
      scanf("%d", &n);
      while (scanf("%s %d %d\n", tipo, &ci, &cj) == 3) {
         switch (tipo[0]) {
            case 'c': adiciona(ci, cj); break;
            case 'q': bfs(ci, cj); break;
         }
      }
      printf("%d,%d\n", suc, unsuc);
   }
   return 0;
}


Thanks.

[elmariachi1414]

There is a great article about "Union Find operation" algorithm here:
http://valis.cs.uiuc.edu/~sariel/teach/2004/b/webpage/lec/22_uf.pdf

[darkos32]

this is my code :

Code: Select all

CODE REMOVED


what's wrong with my code ?thanks.

[rio]

hint:

Code: Select all

#define max 200


----
!! Don't open a new thread if there is a thread already for the problem.

[darkos32]

yep...i've changed to 1000,but i'm now got WA...

[rio]

hint2:

Code: Select all

1

1
q 1 1


hint3:
There is a bug in connect(int, int).

[darkos32]

i've changed the code to :

Code: Select all

CODE REMOVED


but i've still got WA...