OJ Board

Posted: **Mon Apr 05, 2004 2:40 pm**

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

Posted: **Tue Apr 06, 2004 11:35 am**

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

Posted: **Tue Apr 06, 2004 4:52 pm**

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

Posted: **Tue Aug 31, 2004 5:50 am**

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

Posted: **Tue Aug 31, 2004 2:18 pm**

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

Posted: **Wed Sep 01, 2004 3:47 am**

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

Posted: **Wed Jul 05, 2006 4:56 am**

Multiple input no longer applies.

Posted: **Mon Aug 27, 2007 2:10 am**

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

Posted: **Mon Aug 27, 2007 2:52 am**

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**

I've got AC !!!

Posted: **Wed Nov 05, 2008 6:54 pm**

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

Posted: **Thu Nov 06, 2008 5:06 pm**

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.

Posted: **Thu Nov 06, 2008 8:41 pm**

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

Posted: **Wed Sep 04, 2013 11:01 pm**

Shadek, for input:

Code: Select all

My AC output is:

Code: Select all

Your output is:

Code: Select all

In your output there is no path from 2 to 1.

Posted: **Thu Sep 05, 2013 2:31 pm**

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

My sorted output according to above criterion:

Code: Select all

I found no difference. What's wrong?

OJ Board

610 - Street Directions

610 - Street Directions

Re: 610 street directions. RTE?

Re: 610 street directions. RTE?

610 - Street Directions - Why WRONG?

Re: 610 - Street Directions - Why WRONG?

Re: 610 - Street Directions - Why WRONG?

610 test cases please !!!

Some tests

Re: 610 - Street Directions

Re: 610 - Street Directions

Re: 610 - Street Directions

Re: 610 - Street Directions

Re: 610 - Street Directions