## 610 - Street Directions

All about problems in Volume 6. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

CDiMa
Experienced poster
Posts: 214
Joined: Fri Oct 17, 2003 5:49 pm
Location: Genova

### 610 - Street Directions

I'm trying to solve prob 610 but I'm getting RTE consistently

The problem statement says that intersections are numbered from 1 to n and maximum number of intersections is 1000. It says also that at most 4 streets meet at each intersection.
So I allocate space for 1000 intersections and 4000 streets...

Is there something that I'm overlooking?

Thanks in advance for any help!

Claudio

CDiMa
Experienced poster
Posts: 214
Joined: Fri Oct 17, 2003 5:49 pm
Location: Genova

### Re: 610 street directions. RTE?

CDiMa wrote:I'm trying to solve prob 610 but I'm getting RTE consistently

The problem statement says that intersections are numbered from 1 to n and maximum number of intersections is 1000. It says also that at most 4 streets meet at each intersection.
So I allocate space for 1000 intersections and 4000 streets...
Since noone replies, here is an update on my experiments on this prob.
I doubled the number of intersections and increased to 100 the streets that may insist on the same intersection. This way I avoid RTE and get WA.

Since the problem statement is clear on the sizes of input data, I think I fail to get input correctly.

Here is a snippet of my code:
[c]#define MAXV 1000

int E[2*MAXV+1][101];
/* ... */
while(scanf("%d %d",&maxV,&maxE)==2){
if(!maxV && !maxE) return(0);
for(i=maxV;i>0;i--) {
E[0]=0;
};
for(i=maxE;i>0;i--){
scanf("%d %d",&v,&w);
E[v][++E[v][0]]=w;
E[w][++E[w][0]]=v;
};
/* ... */
};
[/c]
E[0] contains the number of streets that insist on on itersection i and E[1] to E[E[0]]
are the intersections adiacent to i.
I expected to need only E[MAXV+1][5] to store the input data...
So what am I missing?

Ciao!!!

Claudio

CDiMa
Experienced poster
Posts: 214
Joined: Fri Oct 17, 2003 5:49 pm
Location: Genova

### Re: 610 street directions. RTE?

CDiMa wrote:Since the problem statement is clear on the sizes of input data, I think I fail to get input correctly.
[...]
So what am I missing?
Multiple inputs

Now I get a very fast WA

Ciao!!!

Claudio

wanderley2k
New poster
Posts: 28
Joined: Mon Mar 01, 2004 11:29 pm

### 610 - Street Directions - Why WRONG?

Hi,

I tried to solve 610, but i got WA.

I implemented the code for discovery brigded in graph and for my test cases my program be correct.

My code:

[cpp]
/*
* encontrar todos as pontes do grafo em TEMPO LINEAR!!
*
*/

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define D(x)
#define MAX_VERTICES 1010

bool adj[MAX_VERTICES][MAX_VERTICES];
bool res[MAX_VERTICES][MAX_VERTICES];
int low[MAX_VERTICES];
int pre[MAX_VERTICES];
int count;
int numVertices;

void bridgeR(int i, int w) {
int j;

pre = count++;
low = pre;

for (j = 0; j < numVertices; j++) {
if (!adj[j]) continue;

if (!res[j] && !res[j]) {
res[j] = true;
}

if (pre[j] == -1) {

bridgeR(j, i);
if (low > low[j]) {
low = low[j];
}
if (low[j] == pre[j]) {
//printf("%d %d\n", j, i);
res[j] = true;
res[j][i] = true;
}
}
else if (j != w) {
if (low[i] > pre[j]) {
//printf(".\n");
low[i] = pre[j];
}
}
}
}

void imprimir(bool matriz[MAX_VERTICES][MAX_VERTICES]) {
int i, j;
for (i = 1; i < numVertices; i++) {
for (j = 1; j < numVertices; j++) {
printf("%d ", matriz[i][j]);
}
printf("\n");
}
}

int main() {
int i, j, k;
int n, m;
int inst = 1;
int cases;

scanf("%d", &cases);
for (; cases > 0; cases--) { // multiple input
//while (scanf("%d %d", &n, &m) == 2) {
scanf("%d %d", &n, &m);
if (n == 0 && m == 0) {
break;
}

if (inst > 1) {
printf("\n");
}
printf("%d\n\n", inst++);

numVertices = ++n;

for (i = 0; i < numVertices; i++) {
pre[i] = -1;
}

memset(adj, false, sizeof(adj));
memset(res, false, sizeof(res));

/* Lendo adjacencia */
for (i = 0; i < m; i++) {
scanf("%d %d", &j, &k);
adj[j][k] = true;
adj[k][j] = true;
}

count = 0;

for (i = 1; i < numVertices; i++) {
if (pre[i] == -1) {
bridgeR(i, i);
}
}

for (i = 1; i < numVertices; i++) {
for (j = 1; j < numVertices; j++) {
if (res[i][j]) {
printf("%d %d\n", i, j);
}
}
}

printf("#");
}
return 0;
}

[/cpp]

Have the input??

Thanks,

Wanderley

CDiMa
Experienced poster
Posts: 214
Joined: Fri Oct 17, 2003 5:49 pm
Location: Genova

### Re: 610 - Street Directions - Why WRONG?

wanderley2k wrote:Hi,

I tried to solve 610, but i got WA.

I implemented the code for discovery brigded in graph and for my test cases my program be correct.
Your code fails on multiple inputs.
When it finds the couple of zero indicating the end of the first case it exits without processing the remaining cases.

Ciao!!!

Claudio

wanderley2k
New poster
Posts: 28
Joined: Mon Mar 01, 2004 11:29 pm

### Re: 610 - Street Directions - Why WRONG?

CDiMa wrote:Your code fails on multiple inputs.
When it finds the couple of zero indicating the end of the first case it exits without processing the remaining cases.
Claudio
Ok, I read the problem again and find the error..

Thanks

I learned the lession: READ READ READ THE INPUT!

Wanderley

daveon
Experienced poster
Posts: 229
Joined: Tue Aug 31, 2004 2:41 am
Location: TORONTO, CANADA
Multiple input no longer applies.

chileno
New poster
Posts: 3
Joined: Mon Aug 27, 2007 2:05 am

### 610 test cases please !!!

Hi, I tried a lot of tests and I think the output is correct. Could you give me some test cases ??? Thanks !!

chileno
New poster
Posts: 3
Joined: Mon Aug 27, 2007 2:05 am

### Some tests

Here are some tests that I tried.

Input:
3 3
1 2
1 3
2 3
7 10
1 2
1 3
2 4
3 4
4 5
4 6
5 7
6 7
2 5
3 6
7 9
1 2
1 3
1 4
2 4
3 4
4 5
5 6
5 7
7 6
3 2
1 2
2 3
2 1
1 2
4 5
1 2
1 3
1 4
2 3
3 4
5 5
1 2
2 3
3 4
4 5
5 1
4 3
1 4
2 3
3 4
0 0

Output:
1

1 2
2 3
3 1
#
2

1 2
2 4
3 1
3 6
4 3
5 2
5 4
6 4
6 7
7 5
#
3

1 2
2 4
3 1
4 1
4 3
4 5
5 4
5 6
6 7
7 5
#
4

1 2
2 1
2 3
3 2
#
5

1 2
2 1
#
6

1 2
2 3
3 1
3 4
4 1
#
7

1 2
2 3
3 4
4 5
5 1
#
8

1 4
2 3
3 2
3 4
4 1
4 3
#

chileno
New poster
Posts: 3
Joined: Mon Aug 27, 2007 2:05 am
I've got AC !!!

tryit1
Experienced poster
Posts: 119
Joined: Sun Aug 24, 2008 9:09 pm

### Re: 610 - Street Directions

My algorithm is
I find all the bridges ,store the orientation bridge with (x,y) as orient[x][y]=orient[y][x]=1
For every other edge in DFS if x is parent of y , then orient[x][y]=1.
All the other unmarked edges in arr[j] (adjacency matrix) is orient[y][x]=1;

Any inputs for which this fails.

Code: Select all

``````
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define MAX 1010
int N, E;
int arr[MAX][MAX], orient[MAX][MAX];
int visit[MAX], low[MAX], num[MAX], tme;

/* tme is time
* orient is whether the edge runs from x -> y or y->x
* For a bridge it is both
*
* */

/*Find the bridges in the graph */
void
dfs (int x, int par, int isroot)
{

num[x] = ++tme;
visit[x] = 1;
low[x] = num[x];
int y;
for (y = 1; y <= N; y++)
{
if (y != par)
{
if (arr[x][y])
{
if (!visit[y])
{
/* y is successor of x in dfs , go from x->y */
orient[x][y] = 1;
dfs (y, x, false);
if (low[y] == num[y])	//&& low[i]>=num[i])
{
//            printf ("x,y=%d,%d\n", x, y);
orient[x][y] = 1;
orient[y][x] = 1;
}
low[x] = min (low[x], low[y]);
}
else
{
low[x] = min (low[x], num[y]);
}
}
}
}

}

int
main ()
{
int tc = 0;
while (scanf (" %d %d", &N, &E) != EOF)
{
//if(f) printf("\n");
if (!N && !E)
break;
++tc;
memset (arr, 0, sizeof (arr));
memset (orient, 0, sizeof (orient));
memset (visit, 0, sizeof (visit));
memset (low, 0, sizeof (low));
memset (num, 0, sizeof (num));
tme = 0;
int x, i, y, j;
for (j = 0; j < E; j++)
{
scanf (" %d %d", &x, &y);
arr[x][y] = 1;
arr[y][x] = 1;
}

for (i = 1; i <= N; i++)
if (!visit[i])
{
dfs (i, i, true);
}

printf ("%d\n\n", tc);

for (i = 1; i <= N; i++)
{
for (j = 1; j <= N; j++)
{
if (arr[i][j])
{
if (!orient[i][j])
orient[j][i] = 1;
}
}
}

for (i = 1; i <= N; i++)
{
for (j = 1; j <= N; j++)
{
if (orient[i][j])
{
printf ("%d %d\n", i, j);
if ((i != j) && orient[j][i])
{
printf ("%d %d\n", j, i);
orient[j][i] = 0;
}
}
}
}

printf ("#\n");
}

return 0;
}

``````

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

### Re: 610 - Street Directions

tryit1 wrote:All the other unmarked edges in arr[j] (adjacency matrix) is orient[y][x]=1;

tryit1 wrote:

Code: Select all

``````      for (i = 1; i <= N; i++)
{
for (j = 1; j <= N; j++)
{
if (arr[i][j])
{
if (!orient[i][j])
orient[j][i] = 1;
}
}
}``````
Well, your mistake is in this step. You don't need it (there's no way to fix it), instead you need to change your DFS code a little.

When you do a DFS search on an undirected graph, the edges of the graph can be classified as either tree edges and back edges (google for definitions). Some of the tree edges can be bridges (but a back edge can never be a bridge).

Your code orients the bridge edges two-way, non-bridge tree edges away from the root - so far this is all correct. But then a step in your algorithm mentioned above does something strange with the back edges - it orients each back edge to be from a higher-numbered vertex to a lower-numbered vertex. This is, of course, just completely arbitrary, and can't be always right (especially with larger graphs). Try to think of a better way to deal with back edges.

tryit1
Experienced poster
Posts: 119
Joined: Sun Aug 24, 2008 9:09 pm

### Re: 610 - Street Directions

mf wrote:
tryit1 wrote:All the other unmarked edges in arr[j] (adjacency matrix) is orient[y][x]=1;

tryit1 wrote:

Code: Select all

``````      for (i = 1; i <= N; i++)
{
for (j = 1; j <= N; j++)
{
if (arr[i][j])
{
if (!orient[i][j])
orient[j][i] = 1;
}
}
}``````
Well, your mistake is in this step. You don't need it (there's no way to fix it), instead you need to change your DFS code a little.

When you do a DFS search on an undirected graph, the edges of the graph can be classified as either tree edges and back edges (google for definitions). Some of the tree edges can be bridges (but a back edge can never be a bridge).

Your code orients the bridge edges two-way, non-bridge tree edges away from the root - so far this is all correct. But then a step in your algorithm mentioned above does something strange with the back edges - it orients each back edge to be from a higher-numbered vertex to a lower-numbered vertex. This is, of course, just completely arbitrary, and can't be always right (especially with larger graphs). Try to think of a better way to deal with back edges.
With the change

Code: Select all

``````             else // x -> y is a back edge
{

if(num[y] < num[x]) orient[x][y]=1;

low[x] = min (low[x], num[y]);
}
``````
thanks mf, i got it accepted with in the backedge with the above step. I had this code accepted on around 4 other problems, so thought it would be correct.
and removing the other 2 loops altogether

My question is we mark all the forward edges and bridges . Now the left over edges are backedges ? Aren't they ?

Can't we have the direction of back edges based on the time when they were seen ?
I found a way to orient them ie

Code: Select all

``````      if (arr[i][j]) // all the forward edges and bridges are oriented
{
if (!orient[i][j] && !orient[j][i]) // this mean this edge is a backedge and it is not oriented yet , now check the times of i and j in the dfs and orient them
if(num[i] < num[j]) orient[j][i]=1 else orient[i][j]=1;
}
}
``````
got AC thanks again mf

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 610 - Street Directions

Shadek, for input:

Code: Select all

``````53 73
2 1
2 11
3 1
4 2
5 3
6 5
7 1
8 3
9 8
10 2
11 7
12 5
13 1
13 15
14 4
15 10
15 30
16 5
17 8
18 3
19 4
20 4
21 20
21 52
22 18
22 28
23 14
23 52
24 23
25 18
25 30
26 11
26 52
27 7
28 8
29 23
29 28
30 14
31 12
31 27
32 20
32 46
33 22
33 50
34 33
35 25
35 33
36 21
36 38
37 18
38 21
38 34
39 28
39 48
40 22
41 16
41 25
42 20
42 30
43 24
43 50
44 26
45 26
46 9
46 13
47 13
48 14
49 47
50 47
51 50
52 32
53 11
53 39
0 0
``````
My AC output is:

Code: Select all

``````1

7 1
3 1
4 2
21 20
38 21
18 3
13 1
13 46
47 49
49 47
50 33
24 23
43 24
50 43
50 51
51 50
47 50
13 47
15 13
10 2
15 10
30 15
30 14
42 20
30 42
25 30
35 33
25 35
16 5
41 16
25 41
18 25
18 37
37 18
22 18
28 8
29 23
28 29
48 14
39 48
53 11
39 53
28 39
22 28
22 40
40 22
33 22
34 33
38 34
36 38
21 36
52 21
26 11
26 44
44 26
26 45
45 26
52 26
52 32
23 52
14 23
4 14
4 19
19 4
20 4
32 20
46 32
9 46
8 9
8 17
17 8
3 8
5 3
5 6
6 5
12 5
31 12
27 31
7 27
11 7
2 11
1 2
#
``````
Your output is:

Code: Select all

``````1

47 49
49 47
50 51
51 50
18 37
37 18
22 40
40 22
26 44
44 26
26 45
45 26
4 19
19 4
8 17
17 8
5 6
6 5
1 2
1 3
1 7
1 13
2 11
2 4
2 10
3 5
3 8
3 18
4 14
4 20
5 12
5 16
7 11
7 27
8 9
8 28
9 46
10 15
11 26
11 53
12 31
13 15
13 46
13 47
14 23
14 30
14 48
15 30
16 41
18 22
18 25
20 21
20 32
20 42
21 52
21 36
21 38
22 28
22 33
23 52
23 24
23 29
24 43
25 30
25 35
25 41
26 52
27 31
28 29
28 39
30 42
32 46
32 52
33 50
33 34
33 35
34 38
36 38
39 48
39 53
43 50
47 50
#
``````
In your output there is no path from 2 to 1.
Check input and AC output for thousands of problems on uDebug!

Shadek
New poster
Posts: 2
Joined: Thu Sep 05, 2013 2:23 pm

### Re: 610 - Street Directions

hi Brianfry,

After sorting your output according to edge (a,b)
if( a<b) insert (a,b)
else insert(b,a)
then sorting the edges according to a, if a is same for some edges,then sort according to smaller b

Your sorted output:

Code: Select all

``````1 2
1 3
1 7
1 13
2 4
2 10
2 11
3 5
3 8
3 18
4 14
4 19
4 19
4 20
5 6
5 6
5 12
5 16
7 11
7 27
8 9
8 17
8 17
8 28
9 46
10 15
11 26
11 53
12 31
13 15
13 46
13 47
14 23
14 30
14 48
15 30
16 41
18 22
18 25
18 37
18 37
20 21
20 32
20 42
21 36
21 38
21 52
22 28
22 33
22 40
22 40
23 24
23 29
23 52
24 43
25 30
25 35
25 41
26 44
26 44
26 45
26 45
26 52
27 31
28 29
28 39
30 42
32 46
32 52
33 34
33 35
33 50
34 38
36 38
39 48
39 53
43 50
47 49
47 49
47 50
50 51
50 51
``````
My sorted output according to above criterion:

Code: Select all

``````1 2
1 3
1 7
1 13
2 4
2 10
2 11
3 5
3 8
3 18
4 14
4 19
4 19
4 20
5 6
5 6
5 12
5 16
7 11
7 27
8 9
8 17
8 17
8 28
9 46
10 15
11 26
11 53
12 31
13 15
13 46
13 47
14 23
14 30
14 48
15 30
16 41
18 22
18 25
18 37
18 37
20 21
20 32
20 42
21 36
21 38
21 52
22 28
22 33
22 40
22 40
23 24
23 29
23 52
24 43
25 30
25 35
25 41
26 44
26 44
26 45
26 45
26 52
27 31
28 29
28 39
30 42
32 46
32 52
33 34
33 35
33 50
34 38
36 38
39 48
39 53
43 50
47 49
47 49
47 50
50 51
50 51
``````
I found no difference. What's wrong?