280 - Vertex

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

Moderator: Board moderators

Ferdous
New poster
Posts: 26
Joined: Sun Dec 14, 2003 1:17 pm
Location: Dhaka, Bangladesh
Contact:

Post by Ferdous »

Don't I need to search for every query? I can't understand what you have told. Would you please explain a little more?
I am destined to live on this cruel world........

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

Post by CDiMa »

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

4
1 2 0
2 3 0
3 4 0
0
2 2 1
0
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

Ferdous
New poster
Posts: 26
Joined: Sun Dec 14, 2003 1:17 pm
Location: Dhaka, Bangladesh
Contact:

Post by Ferdous »

Thanks a lot, Claudio for your lucid explanation.
I am destined to live on this cruel world........

Ghust_omega
Experienced poster
Posts: 115
Joined: Tue Apr 06, 2004 7:04 pm
Location: Venezuela

280 - Vertex

Post by Ghust_omega »

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

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

Code: Select all

2 1 3
2 1 3
2 1 2
1 1
0
Thanks in advance
Keep posting !!

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

Re: 280 Vertex WA Help!!

Post by CDiMa »

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

Ghust_omega
Experienced poster
Posts: 115
Joined: Tue Apr 06, 2004 7:04 pm
Location: Venezuela

Post by Ghust_omega »

Hi !! CDiMa thanks for your answer and by the I/O, my program gives the same answers, :cry: , if you have more I/O please post here thanks again
Thanks in advance
Keep posting !!

Mohammad Mahmudur Rahman
Experienced poster
Posts: 154
Joined: Sat Apr 17, 2004 9:34 am
Location: EEE, BUET

Post by Mohammad Mahmudur Rahman »

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?
You should never take more than you give in the circle of life.

Ghust_omega
Experienced poster
Posts: 115
Joined: Tue Apr 06, 2004 7:04 pm
Location: Venezuela

Post by Ghust_omega »

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

Ghust_omega
Experienced poster
Posts: 115
Joined: Tue Apr 06, 2004 7:04 pm
Location: Venezuela

Post by Ghust_omega »

I Solved :lol: Thanks to all that try to help me :D



Thanks in advance
Keep posting !!

Mohammad Mahmudur Rahman
Experienced poster
Posts: 154
Joined: Sat Apr 17, 2004 9:34 am
Location: EEE, BUET

Post by Mohammad Mahmudur Rahman »

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. :D Nice to know that you've got AC.
You should never take more than you give in the circle of life.

minskcity
Experienced poster
Posts: 199
Joined: Tue May 14, 2002 10:23 am
Location: Vancouver

keep getting WA.....

Post by minskcity »

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]

Ghust_omega
Experienced poster
Posts: 115
Joined: Tue Apr 06, 2004 7:04 pm
Location: Venezuela

Post by Ghust_omega »

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

Ghust_omega
Experienced poster
Posts: 115
Joined: Tue Apr 06, 2004 7:04 pm
Location: Venezuela

Post by Ghust_omega »

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

Zuberul
New poster
Posts: 28
Joined: Sun Oct 24, 2004 9:46 pm
Location: dhaka
Contact:

Post by Zuberul »

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

Jemerson
Learning poster
Posts: 59
Joined: Mon Feb 02, 2004 11:19 pm
Contact:

280 - Vertex - Floyd Warshall WA - HELP!

Post by Jemerson »

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");
      }
   }
}
UFCG Brazil - Computer Science graduate student
http://acm.uva.es/problemset/usersnew.php?user=54806 ... and going up!

Post Reply

Return to “Volume 2 (200-299)”