runtah: UVa 627 The Net

Sunday, September 25, 2016

UVa 627 The Net

Pretty simple and somewhat forced towards the solution.
Counting number of nodes and shortest path. You have to print the path too.
Its simply BFS. The pi[ ] array comes handy to print the path.

Method: BFS (Use the pi array)


#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <queue>
#include <algorithm>

#define WHITE 0
#define GREY 1
#define BLACK 3
#define INF 0
#define NIL -1

using namespace std;

bool color[400], adj[400][400];
int d[400], p[400];
char in[100000];

bool bfs( int s, int des, int n ) {
 int u, v;
 for (u=0 ; u<=300 ; u++) {
 color[u] = WHITE;
 d[u] = INF;
 p[u] = NIL;
 }
 color[s] = GREY;
 d[s] = 0;
 p[s] = NIL;
 
 queue<int> q;
 q.push(s);
 while (!q.empty()) {
 u = q.front();
 q.pop();
 for (v=1 ; v<=n ; v++) {
 if (adj[u][v] && color[v]==WHITE) {
 color[v] = GREY;
 d[v] = d[u]+1;
 p[v] = u;
 q.push(v);
 if (v == des) {
 return true;
 
 }
 }
 }
 color[u] = BLACK;
 }
 return false;
}

void print_path(int v) {
 int i, j, pr[1000];
 for (i=v, j=0 ; i>0 ; i=p[i], j++) pr[j] = i;
 for (--j ; j>0 ; j--) printf("%d ",pr[j]);
 printf("%d ",pr[j]); //|Last one cant have
} //|cant have blank space
 //|after it

int main( void ) {


 int i, j, c, n, u, v, nodes, conn;
 char *p;

 while ( scanf("%d",&nodes) == 1 ) {
 getchar(); // Back off for gets()
 
 for (i=0 ; i<=300 ; i++) { 
 for (j=0 ; j<=300 ; j++) adj[i][j] = false;
 }
 
 n = nodes;
 
 while (nodes--) {
 gets(in);
 p = strtok(in,"-,");
 sscanf(p,"%d",&i);
 p = strtok(NULL,"-,");
 while (p) {
 sscanf(p,"%d",&c);
 adj[i][c] = true; //|Connections are !bidirectional
 p = strtok(NULL,"-,");
 }
 }
 
 
 scanf("%d",&conn);
 
 printf("----- ");
 
 for (i=1 ; i<=conn ; i++) {
 scanf("%d %d",&u, &v);
 if (bfs(u,v,n)) {
 print_path( v );
 } else {
 printf("connection impossible ");
 }
 }
 }
}

Go to link download