Page 1 of 2

610 - Street Directions

Posted: Mon Apr 05, 2004 2:40 pm
by CDiMa
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

Re: 610 street directions. RTE?

Posted: Tue Apr 06, 2004 11:35 am
by CDiMa
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

Re: 610 street directions. RTE?

Posted: Tue Apr 06, 2004 4:52 pm
by CDiMa
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 :oops:

Now I get a very fast WA ;)

Ciao!!!

Claudio

610 - Street Directions - Why WRONG?

Posted: Tue Aug 31, 2004 5:50 am
by wanderley2k
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

Re: 610 - Street Directions - Why WRONG?

Posted: Tue Aug 31, 2004 2:18 pm
by CDiMa
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

Re: 610 - Street Directions - Why WRONG?

Posted: Wed Sep 01, 2004 3:47 am
by wanderley2k
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! :D


Wanderley

Posted: Wed Jul 05, 2006 4:56 am
by daveon
Multiple input no longer applies.

610 test cases please !!!

Posted: Mon Aug 27, 2007 2:10 am
by chileno
Hi, I tried a lot of tests and I think the output is correct. Could you give me some test cases ??? Thanks !! :D

Some tests

Posted: Mon Aug 27, 2007 2:52 am
by chileno
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
#

Posted: Mon Aug 27, 2007 6:45 pm
by chileno
I've got AC !!! :P

Re: 610 - Street Directions

Posted: Wed Nov 05, 2008 6:54 pm
by tryit1

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



Re: 610 - Street Directions

Posted: Thu Nov 06, 2008 5:06 pm
by mf
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.

Re: 610 - Street Directions

Posted: Thu Nov 06, 2008 8:41 pm
by tryit1
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

Re: 610 - Street Directions

Posted: Wed Sep 04, 2013 11:01 pm
by brianfry713
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.

Re: 610 - Street Directions

Posted: Thu Sep 05, 2013 2:31 pm
by Shadek
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?