280 - Vertex

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

[CDiMa]

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]

Thanks a lot, Claudio for your lucid explanation.

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

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]

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

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

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

I Solved Thanks to all that try to help me



Thanks in advance
Keep posting !!

[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. Nice to know that you've got AC.

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

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]

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]

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]

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