OJ Board

Posted: **Tue May 09, 2006 9:44 pm**

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

Posted: **Tue May 09, 2006 9:49 pm**

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

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.

Posted: **Tue May 09, 2006 10:38 pm**

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

Posted: **Tue May 09, 2006 11:20 pm**

A very straightforward input to show your error

Code: Select all

Posted: **Wed May 10, 2006 4:41 am**

thnx mamun vai

Posted: **Fri Jul 14, 2006 8:23 pm**

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"

Posted: **Sat Jul 15, 2006 4:27 am**

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

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.

Posted: **Sat Jul 15, 2006 6:38 pm**

You are right

I use the method and got AC on 793 and 10583

Thanks your help

Posted: **Mon Sep 04, 2006 3:34 pm**

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.

Posted: **Sat Oct 14, 2006 9:55 pm**

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

Posted: **Wed Feb 14, 2007 5:01 am**

this is my code :

Code: Select all

CODE REMOVED

what's wrong with my code ?thanks.

Posted: **Wed Feb 14, 2007 6:19 am**

hint:

Code: Select all

#define max 200

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

Posted: **Wed Feb 14, 2007 7:52 am**

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

Posted: **Wed Feb 14, 2007 8:21 am**

hint2:

Code: Select all

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

Posted: **Wed Feb 14, 2007 8:37 am**

i've changed the code to :

Code: Select all

CODE REMOVED

but i've still got WA...

OJ Board

793 - Network Connections

793 - WA

793 RUNTIME ERROR SIGNAL 11 ?

sad

sad