11838 - Come and Go

[sitz]

Hi All !
I was trying this question from the Brazilian Contest. Though, it seems to be standard Floyd-Warshall Algorithm, I was using simpler queue implementation.
I think my approach is correct, but, getting TLE Any reasons for TLE in this code :

Code: Select all

#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>

typedef unsigned int uint;
typedef long long int64;
typedef unsigned long long uint64;

using namespace std;

int main(){
    while(true){
                int N, test;
                int i, j, k;
                cin>>N>>test;
                if(N==0 && test==0)
                        break;
                bool mat[N][N];
                memset( mat, false, sizeof(bool)*N*N );
                while(test--){
                              int X, Y, ctr;
                              cin>>X>>Y>>ctr;
                              if(ctr == 1)
                                     mat[X-1][Y-1] = true;
                              else{
                                   mat[X-1][Y-1] = true;
                                   mat[Y-1][X-1] = true;
                              }
                }
                for(i=0; i<N; i++){
                         queue<int> que;
                         bool stat[N][N];
                         memset( stat, false, sizeof(bool)*N*N );
                         for(j=0; j<N; j++){
                                  if(mat[i][j] && !stat[i][j] && i!=j){
                                               que.push(j);
                                               stat[i][j]=true;
                                  }
                         }
                         while(!que.empty()){
                                           int ind = que.front();
                                           mat[i][ind] = true;
                                           for(j=0; j<N; j++){
                                                    if(mat[ind][j] && !stat[ind][j] && ind!=j){
                                                                   que.push(j);
                                                                   stat[ind][j]=true;
                                                    }
                                           }
                                           que.pop();
                         }
                }
                int cnt=0;
                for(i=0; i<N; i++)
                         for(j=0; j<N; j++)
                                  cnt+=mat[i][j];
                if(cnt == N*N)
                       cout<<"1\n";
                else
                    cout<<"0\n";
    }
    return 0;
}

Thanx in advance

[Khongor_SMCS]

Problem is asking the given directed graph is connected or not.
You can solve it using Tarjan's algorithm.

[pdwd]

You can use dfs to find strongly connected components and check if there is only 1 such component.

[sitz]

As I told before... I know that it can be solved by standard graph algorithm and, I have done it too with "Floyd-Warshall" Algorithm.
But, can anyone tell me is it possible to do the same by QUEUE implementation as in my above code ?

And if yes, then where is the problem in my code... It gives TLE when submitted.. though complexity seems to be the same as "Floyd-Warshall"

[krien]

The main problem of floyd-warshall is the complexity of the algorithm O(n^3) while using a bfs or dfs per node the complexity is O(n^2).
I hope that will help you.

[wazaaaap]

Run DFS from each node, after each run, check if you have visited all the nodes, if yes, tmp++ and at the end, if tmp == n print YES otherwise NO.

[saiful_sust]

it's a easy problem..
It can be solve with standard SCC algorithm

• IMPOSSIBLE MEANS I M POSSIBLE

[Shafaet_du]

sample I/O;

Code: Select all

3 3
1 2 2
1 3 1
2 3 1
5 7
1 5 2
1 2 2
2 5 1
2 4 1
5 3 1
3 4 1
2 3 1
5 7
1 5 2
1 2 2
2 5 1
2 4 1
5 3 2
3 4 2
2 3 1
0 0

output from my ac code:

Code: Select all

0
0
1

[sitz]

@Shafeet_du : My TLE code (given above) aslo gives the same outputs...
But, can we do it the way I have done it ? Or, not ?

[Igor9669]

Certanly you will get TLE on this problem with Floyd!

It could be solve with simple dfs or bfs with little modification!

[sitz]

Hi Igor9669 !
But, I don't understand how people can't understand the simple question that I have posted here
I said I have got Accepted with a time of around 0.338 s using Floyd-Warshall Algorithm...

I just wanted to ask if the above implementation using queues can be optomized to get Ac or its not possible at all

PS-1 : Above code is different than that with which I got Accepted...
PS-2 : Floyd Warshall doesn't give TLE at all

[Igor9669]

I couldn't belive that Floyd could get Ac here....
it complexity O(n^3), where n=2000, how it could be pass at 2 sec???

[sitz]

Well, I thought the same way, but, actually it did pass
For ur belief you can check the verdict of judge here : http://felix-halim.net/uva/hunting.php? ... hrivastava

[Igor9669]

May be bad tests there....((
Or you make a mistake in complexity of your algo...
Your implementation with queue got TLE,because it's O(N^3)!

[Shafaet_du]

Floyd should get TLE with a good data set.