## 11838 - Come and Go

Moderator: Board moderators

sitz
New poster
Posts: 9
Joined: Sat Oct 10, 2009 10:29 pm

### 11838 - Come and Go

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;
}
``````

Khongor_SMCS
New poster
Posts: 15
Joined: Thu Jun 18, 2009 12:01 pm
Contact:

### Re: 11838 - Come And Go

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

pdwd
New poster
Posts: 19
Joined: Sat May 15, 2010 4:35 pm

### Re: 11838 - Come And Go

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

sitz
New poster
Posts: 9
Joined: Sat Oct 10, 2009 10:29 pm

### Re: 11838 - Come And Go

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
New poster
Posts: 5
Joined: Mon Sep 20, 2010 12:51 pm

### Re: 11838 - Come And Go

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).

wazaaaap
New poster
Posts: 7
Joined: Thu Sep 23, 2010 12:55 am

### Re: 11838 - Come And Go

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
Learning poster
Posts: 97
Joined: Fri Aug 22, 2008 10:18 pm
Location: CSE.SUST.SYLHET

### Re: 11838 - Come And Go

it's a easy problem..
It can be solve with standard SCC algorithm
• IMPOSSIBLE MEANS I M POSSIBLE

Shafaet_du
Experienced poster
Posts: 147
Joined: Mon Jun 07, 2010 11:43 am
Contact:

### Re: 11838 - Come And Go

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
New poster
Posts: 9
Joined: Sat Oct 10, 2009 10:29 pm

### Re: 11838 - Come And Go

@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
Learning poster
Posts: 85
Joined: Sun Jun 08, 2008 12:58 pm

### Re: 11838 - Come And Go

Certanly you will get TLE on this problem with Floyd!

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

sitz
New poster
Posts: 9
Joined: Sat Oct 10, 2009 10:29 pm

### Re: 11838 - Come And Go

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
Learning poster
Posts: 85
Joined: Sun Jun 08, 2008 12:58 pm

### Re: 11838 - Come And Go

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
New poster
Posts: 9
Joined: Sat Oct 10, 2009 10:29 pm

### Re: 11838 - Come And Go

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
Learning poster
Posts: 85
Joined: Sun Jun 08, 2008 12:58 pm