610 - Street Directions

[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

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

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]

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]

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]

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]

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]

Multiple input no longer applies.

[chileno]

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

[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
#

[chileno]

I've got AC !!!

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

[mf]

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

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]

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

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]

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.

[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?