OJ Board

Posted: **Sat Apr 24, 2004 11:09 am**

Don't I need to search for every query? I can't understand what you have told. Would you please explain a little more?

Posted: **Mon Apr 26, 2004 12:17 pm**

Ferdous wrote:Don't I need to search for every query? I can't understand what you have told. Would you please explain a little more?

Ok, let's make a simple example:

Code: Select all

This digraph can be represented as:

Code: Select all

1-->2-->3-->4

In the first query you do a search from 2 and visit nodes 3 and 4. Now you know that from 2 you reach 3 and 4.
When you process the second query you start from 1 and visit 2,3 and 4. But you already visited the graph starting from 2 earlier. You can add nodes reachable from 2 to the set of nodes reachable from 1 without revisiting the entire graph.

In my program after getting input I generate the sets of unreachable nodes for all nodes in the graph and then simply output the result for every node queried.

Ciao!!!

Claudio

Posted: **Mon Apr 26, 2004 4:32 pm**

Thanks a lot, Claudio for your lucid explanation.

Posted: **Sun Oct 17, 2004 6:50 am**

Hi !! to everyone I get WA, this is my algo, its something i miss ?? please Help me

1. DO Floyd - warshall
2. count the inaccessible vertex and put in a array
3. print the count of inaccessible vertex
4. print the numbers of inaccessible vertex from the array

any I/O will be usefull, or any hints please help

this is some I/O is right??

Input:

Code: Select all

ouput

Code: Select all

Thanks in advance
Keep posting !!

Posted: **Mon Oct 18, 2004 10:16 am**

Ghust_omega wrote: any I/O will be usefull, or any hints please help

this is some I/O is right??
[...]

My AC program gives the same output.

Try this input :

Code: Select all

7
1 2 0
2 3 4 0
3 1 0
4 5 0
5 4 0
6 7 0
7 6 0
0
7 1 2 3 4 5 6 7
0

output:

Code: Select all

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

Ciao!!!

Claudio

Posted: **Mon Oct 18, 2004 2:11 pm**

Hi !! CDiMa thanks for your answer and by the I/O, my program gives the same answers,

, if you have more I/O please post here thanks again
Thanks in advance
Keep posting !!

Posted: **Thu Oct 21, 2004 11:56 pm**

You may try this input

Code: Select all

5
0
5 1 2 3 4 5
4
1 2 3 4 0
2 3 4 0
3 4 0
0
4 1 2 3 4

Meanwhile, what about using DFS?

Posted: **Fri Oct 22, 2004 5:14 am**

Hi !! Mohammad Mahmudur Rahman, thanks for the I/O This is the ouput:

Code: Select all

5 1 2 3 4 5
5 1 2 3 4 5
5 1 2 3 4 5
5 1 2 3 4 5
5 1 2 3 4 5
1 1
2 1 2
3 1 2 3
4 1 2 3 4

I think that floyd solve the problem too, any suggestions??
Thanks in advance
Keep posting !!

Posted: **Fri Oct 22, 2004 6:56 am**

I Solved

Thanks to all that try to help me

Thanks in advance
Keep posting !!

Posted: **Fri Oct 22, 2004 9:26 pm**

I think that floyd solve the problem too

Yes, surely. DFS was just another suggestion which I think to be easier in this case, obviously my personal view only.

Nice to know that you've got AC.

Posted: **Tue Nov 02, 2004 4:17 am**

I don't see what can be possibly wrong with my code, but keep getting WA. I'm using Floyd - Warshall.

[cpp]#include <cstdio>
#include <string>
using namespace std;

char data[201][201];
int ans[201];
int n, m, a, b, cnt;

int main(){

while(scanf("%d", &n) == 1 && n){
memset(data, 0, sizeof(data));
while(scanf("%d", &a) == 1 && a)
while(scanf("%d", &b) == 1 && b){
data[a] = 1;
a ^= b ^= a ^= b;
}

for(int k = 1; k <= n; k++)
for(int i = 1; i <= n; i++)
for(int j = 1; j <= n; j++)
data[j] |= (data[k] && data[k][j]);

scanf("%d", &m);
while(m-- && scanf("%d", &a) == 1){
cnt = 0;
for(int i = 1; i <= n; i++)
if(!data[a]) ans[cnt++] = i;
printf("%d", cnt);
for(int i = 0; i < cnt; i++) printf(" %d", ans);
printf("\n");
}

}

return 0;
}
[/cpp]

Posted: **Wed Nov 03, 2004 1:02 am**

Hi !! minskcity I change something in your code and get AC check your PM isend yur code there
Hope it helps
Keep posting !!

Posted: **Wed Nov 03, 2004 1:02 am**

Hi !! minskcity this is the part I change
[c]
while(scanf("%d", &n) == 1 && n){
memset(data, 0, sizeof(data));
while(scanf("%d", &a) == 1 && a)
while(scanf("%d", &b) == 1 && b){
..............
}

for( k = 1; k <= n; k++)
for( i = 1; i <= n; i++)
for( j = 1; j <= n; j++)
...............

[/c]
Hope it Helps
Keep posting

Posted: **Sun Nov 21, 2004 11:10 pm**

I used just dfs & cant find out why WA?
here is my code

#include<stdio.h>
#include<malloc.h>

#define SIZE 200

typedef struct node{
int paths[SIZE];
int isVisited;
}vertex;

vertex *p;

int reachable;

void DFS(int i)
{
int j;
j=0;
while(p.paths[j]>=0 && p[p.paths[j]].isVisited==-1)
{
p[p.paths[j]].isVisited=1;
reachable++;
DFS(p.paths[j]);
j++;
}
}

void doDFS(int N,int start)
{
int i;
DFS(start);
printf("%d",N-reachable);
for(i=1;i<=N;i++)
{
if(p.isVisited==-1)printf(" %d",i);
}
printf("\n");
}

void refresh()
{
int i,j;
for(i=0;i<SIZE;i++)
{
for(j=0;j<SIZE;j++)
{
p.paths[j]=-1;
}
p.isVisited=-1;
}
}

void main()
{
int N,i,e,j;

p=(vertex*)malloc(SIZE*sizeof(vertex));

while(scanf("%d",&N)==1 && N)
{
refresh();

while(scanf("%d",&i) ==1 && i)
{
while(scanf("%d",&e)==1 && e)
{
j=0;
while(p.paths[j]>=0)j++;
p.paths[j]=e;
}
}
scanf("%d",&i);
while(i-->0)
{
scanf("%d",&j);
reachable=0;
doDFS(N,j);
for(e=0;e<=N;e++)
{
p[e].isVisited=-1;
}
}
}
free(p);
}

Posted: **Tue Aug 23, 2005 8:04 am**

Hi guys, first I'd like to tell u that this one is just the second graph problem I try, so, there may exist some logic trouble. My algorithm works like this:
Define infinity to be 20000 if there is no path between two vertices.
Collect input infos and update the paths.
Use Floyd-Warshall to determine the shortest path between all vertices
For the desired vertex check if there's such a short path.
Output those who doesn't have it.

I've already checked and accepted all suggested inputs, but it keeps on WA. I'd be very thankful if anyone could help me.

Code: Select all

#include <stdio.h>

int n, src, dst, numb, v;

int main() {
   
   while(scanf("%d", &n) == 1 && n){
      long graph [201][201];

      for (int i = 1; i <= n; i++) 
         for (int j = 1; j <= n; j++) 
             graph[i][j] = 20000;

      while (scanf("%d", &src) == 1 && src) {
          while (scanf("%d", &dst) == 1 && dst) {
              graph[src][dst] = 1;
              src = dst;
          }
      }
                  
      /* Floyd Warshall */
      for (int k = 1; k <= n; k++) {
          for (int t = 1; t <= n; t++) {
              for (int j = 1; j <= n; j++) {
                 if (graph[t][k] + graph[k][j] < graph[t][j]) {
                     graph[t][j] = graph[t][k] + graph[k][j];
                 }
              }
          }
      }
      
      scanf("%d", &numb);
      while(numb-- && scanf("%d", &v) == 1){
          int contador = 0;
          for (int j = 1; j <= n; j++) 
             if (graph[v][j] >= 20000) contador++;
          printf("%d", contador);
          for (int j = 1; j <= n; j++) 
             if (graph[v][j] >= 20000) printf(" %d", j);
          printf("\n");
      }
   }
}

OJ Board

280 - Vertex

280 - Vertex

Re: 280 Vertex WA Help!!

keep getting WA.....

280 - Vertex - Floyd Warshall WA - HELP!