Program runtime is too long

[Matas]

Hello. I need to make a program which must be executed during 1 second, no more. But my program is being timed out if it need to output a lot of data. I think program does calculation quite fast, problem is in output and do not know how to solve it. I replaced standart input to scanning from a file and have found that execution time is more than 4 seconds.(If you need more data for checking, write)
Ex.:
2
2 1
1 2
10 7
1 4
2 6
3 6
3 7
5 9
6 9
9 10

My code:

#include <iostream>
using namespace std;

int main()
{
     int  i, T, n, m, a, b, j, l = 0, p, yes = 0, no = 0, g, tc = 1, j1, u, y;
     cin >> T;
     for(i = 0; i < T; i ++)
     {
         cin >> n >> m;
         int A[m][2];
         for (j1 = 0; j1 < m; j1 ++)
         {
             cin >> a >> b;
             A[j1][0] = a;
             A[j1][1] = b;
         }
         cout << "Case #" << tc << ":" <<endl;
         tc ++;
         int B[m];
         for (j = 1; j <= n; j ++)
         {
             for (u = 0; u < m; u ++)
             {
                 if(j == A[u][0]) {B[l] = A[u][1]; l ++;}
                 if(j == A[u][1]) {B[l] = A[u][0]; l ++;}
             }
             for (g = 0; g < l; g ++)
             {
                 for(y = 0; y < m; y ++)
                 {
                     if(B[g] == A[y][0] )
                     {
                         for(p = 0; p < l; p ++)
                         {if(B[p] != A[y][1]) no ++;
                            else yes ++;}

                         if(yes == 0 && A[y][1] != j)
                         {B[l] = A[y][1];
                         l ++;
                         yes = 0;
                         no = 0;}else{yes = 0; no = 0;}
                     }
                     if(B[g] == A[y][1] )
                     {
                         for(p = 0; p < l; p ++)
                         {if(B[p] != A[y][0]) no ++;
                            else yes ++;}

                         if(yes == 0 && A[y][0] != j)
                         {B[l] = A[y][0];
                         l ++;
                         yes = 0;
                         no = 0;}else{yes = 0; no = 0;}
                     }
                 }
             }
             cout << l << " ";
             l = 0;
         }
     }
}

[tcs]

(MacOSX 2,66 GHz Intel Core i7)

tcs > time ./matas <matas.txt 
Case #1:
1 1 Case #2:
1 6 6 1 6 6 6 0 6 6 
real    0m0.005s
user    0m0.002s
sys     0m0.002s

[TheIdeasMan]

Hi,

How do you know that most of the ET is taken up with output? It's just that you have 4 levels of for loop in your code, so that is likely to make for O(n⁴) so that is quadratic squared - which is not good. Try to aim for algorithms that are some where around O(log n) or O(n)

Is this for an online coding challenge like Euler or Online Judge? If so, the solutions to these are not trivial (brute force doesn't work), so one has to come up with a cunning plan for an algorithm.

@tcs

Just curious: did you use the data from the OPost, or did you get more data from a larger file? I see your input file, just wondering how much data was in it?

Hope all is well :+)

[Matas]

Thanks, TheIdeasMan, for info about loops. Yes, this task is for online coding challenge, but in Codeforces area.
I using my own data, because there are no data file or something, just small example. Also there are several limitations for input (T <= 30; 1 <= n, m <= 10000; 1 <= a <= b <= n), but I know when program is being test ultimate data is always in use.

[tcs]

@TheIdeasMan: Do you think it should be done in usec instead of msec? Ok, the timer resolution isn't the best one ;-)

[TheIdeasMan]

@tcs

No, no, just wondering how much data you used that's all? :+)

Forgive me for thinking that, but you only had 2 test cases in your output.

Now I am pretty sure you know way way more than me, but if you had run the OP's code with the data in the O Post, it might well run Ok, but if you had 10000 items it might not. Any way I am sure you don't need me to point that out. :+)

Maybe the OP is running the Debug version not the Release? Probably much more likely. I have just written some code to do prime numbers up to 2 million, it took about 15 secs in Debug, and less than 0.5sec in Release mode.

Any way regards and Cheers