[UVa] 10926 - How many dependencies

#include <cstdio>
#include <iostream>

using namespace std;

#define init(n) { for (int i=0 ; i<=n ; i++) { visit[i] = false; for (int j=0 ; j<=n ; j++) adj[i][j] = adj[j][i] = false; } }

int n, dep[200], root[200], adj[200][200];
bool visit[200];

int dfs_visit(int s, int src) {

    root[s] = src;
    dep[s] = 0;
    for (int i=1 ; i<=n ; i++) {
        if (!visit[i] && adj[s][i]) {
            visit[i] = true;
            dep[s] += (dfs_visit(i,src)+1);
        }
    }
    return dep[s];
}

void dfs() {

    for (int i=1 ; i<=n ; i++) {
        for (int j=0 ; j<=n ; j++) visit[j] = false;
        dfs_visit(i,i);
    }

}

int main( void ) {

    int t, x, maxdepi, maxdep;

    while (scanf("%d",&n)==1 && n) {

        init(n);

        for (int i=1 ; i<=n ; i++) {
            scanf("%d",&t);
            for (int j=0 ; j<t ; j++) {
                scanf("%d",&x);
                adj[i][x] = true;
            }
        }


        dfs();

        maxdep = -1000;

        for (int i=1 ; i<=n ; i++) {


            if (dep[i]>maxdep) {
                maxdep = dep[i];
                maxdepi = i;

            }
        }

        printf("%d\n",maxdepi);

    }


    return 0;
}

[UVa] 796 - Critical Links

Method: The core idea is behind the DFS. It uses the d[u] data. low[u] contains the index of the topmost and leftmost vertex in the tree that u resides in. It is updated in two conditions. They are
1. If a vertex that is connected with u was visited earlier has a lower d[v] (d[v] is checked because u is part of v's tree then it's low[v] is still not reliable but d[v] is it's most reliable data)
2. If a fresh vertex is visited through u, then u can use that low[v] data and update itself in case v has a higher hierarchy access.
3. If low[v] > d[u], the explanation of this is that low[v] was generated during a traversal from v. During that traversal v could not find any other edge to reach u or any of it's preceding nodes. So, to reach the tree that u resides in, v must use the edge [u,v] which makes it a bridge essentially.

#include <cstdio>
#include <iostream>
#include <vector>
using namespace std;
bool visited[200];
int d[200], low[200], brcount, br[200][200];
vector<int> g[200];
int dfs(int u, int parent, int depth) {
    visited[u] = true;
    d[u] = low[u] = depth;

    for (int i=0 ; i<g[u].size() ; i++) {
        int v = g[u][i];

        if (visited[v] && v!=parent) {
            low[u] = (low[u]<d[v]?low[u]:d[v]);
        }
        if (!visited[v]) {
            dfs(v, u, depth+1);
            low[u] = (low[u]<low[v]?low[u]:low[v]);
            if (low[v]>d[u]) {
                brcount++;
                br[u][v] = br[v][u] = true;
            }
        }
    }

}


int main( void ) {

    //freopen("brg.txt","r+",stdin);

    int n, v, x, e;

    while (~scanf("%d",&n)) {

        for (int i=0 ; i<200 ; i++) {
            g[i].clear();
            visited[i] = false;
            for (int j=0 ; j<200 ; j++) {
                br[i][j] = false;
            }
        }

        for (int i=0 ; i<n ; i++) {
            scanf("%d (%d)",&v,&e);
            for (int j=0 ; j<e ; j++) {
                scanf("%d",&x);
                g[v].push_back(x);
                g[x].push_back(v);
            }
        }

        brcount = 0;

        for (int i=0 ; i<n ; i++) {
            if (!visited[i]) {
                dfs(i, 0, 0);
            }
        }

        printf("%d critical links\n",brcount);
        for (int i=0 ; i<n ; i++) {
            for (int j=i+1 ; j<n ; j++) {
                if (br[i][j]) {
                    printf("%d - %d\n",i,j);
                    br[i][j] = br[j][i] = false;
                }
            }
        }
        printf("\n");
    }

    return 0;
}

[UVa] 10199 - Tourist Guide

The problem uses the concept of Articulation Points. One critical case is when the graph is already disconnected.
Method: For each vertex, I first counted it's child count (dfscount, dfsnum). Then I counted them again after disconnecting that vertex. If both of them aren't same, I incremented the Articulation Point count, because that vertex is an articulation point.

6
sugarloaf
maracana
copacabana
ipanema
corcovado
lapa
7
ipanema copacabana
copacabana sugarloaf
ipanema sugarloaf
maracana lapa
sugarloaf maracana
corcovado sugarloaf
lapa corcovado
5
guanabarabay
downtown
botanicgarden
colombo
sambodromo
4
guanabarabay sambodromo
downtown sambodromo
sambodromo botanicgarden
colombo sambodromo
6
a
b
d
c
e
f
7
a b
a d
d c
b d
c e
c f
e f
7
g
f
e
d
c
b
a
6
a b
b c
c d
d e
e f
f g
7
g
f
e
d
c
b
a
7
a b
b c
c d
d e
e f
f g
g a
7
g
f
e
d
c
b
a
6
a b
b c
c d
d e
e f
f a
6
a
b
c
d
e
f
5
a b
a f
c d
c e
d e
3
a
b
c
2
a b
b c
0

#include <cstdio>
#include <iostream>
#include <string>
#include <map>
#include <vector>


using namespace std;


bool visited[200], con[200][200];
int dfscounter;
int dfs(int v, int n) {
    visited[v] = true;
    dfscounter++;
    for (int i=1 ; i<=n ; i++) {
        if (!visited[i] && con[v][i]) {
            dfs(i, n);
        }
    }
}
map<string, int> cmap;
vector<string> lst;
int artP;
int main( ) {
    int n, e, kase=1;

    //freopen("tourist.txt","r+",stdin);
    //freopen("output.txt","w+",stdout);

    while ( cin >> n ) {

        if (!n) break;

        if (kase>1) cout << endl;

        cmap.clear();
        lst.clear();
        artP = 0;
        for (int i=1 ; i<=n ; i++) {
            string a;
            cin >> a;
            cmap[a] = i;
        }
        cin >> e;
        for (int i=1 ; i<=n ; i++) for (int j=1 ; j<=n ; j++) con[i][j] = false;
        for (int i=1 ; i<=e ; i++) {
            string a, b;
            cin >> a >> b;
            con[ cmap[a] ][ cmap[b] ] = con[ cmap[b] ][ cmap[a] ] = true;
        }
        for (map<string, int>::iterator it=cmap.begin() ; it!=cmap.end() ; it++) {
            int rcount;
            dfscounter=0;
            for (int i=1 ; i<=n ; i++) visited[i] = false;
            dfs(it->second, n);
            rcount = dfscounter;
            for (int i=1 ; i<=n ; i++) visited[i] = false;
            visited[it->second] = true;
            dfscounter=0;
            for (int i=1 ; i<=n ; i++) {
                if (con[ it->second ][i]) {
                    dfs(i, n);
                    break;
                }
            }
            if (rcount>1 && dfscounter!=rcount-1) {
                artP++;
                lst.push_back(it->first);
            }
        }

        printf("City map #%d: %d camera(s) found\n",kase++,lst.size());
        for (int i=0 ; i<lst.size() ; i++) {
            cout << lst[i] << endl;
        }

    }

}

[UVa] 315 - Network

#Articulation Points #Graph #DFS #BFS
Method:
Turn off each node and see if all the other nodes except that are visited or not using DFS
Sample I/O:

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

#include <cstdio>
#include <iostream>
#include <vector>
#include <cstring>
using namespace std;

bool con[200][200];
vector< pair<int, int> > edges;
bool visit[200];

void init_con(int n) {
    for (int i=0 ; i<=n ; i++)
        for (int j=0 ; j<=n ; j++)
            con[i][j] = false;
}

int dfs_visit(int s, int n) {

    int vCount = 1;

    if (visit[s]) return 0;
    visit[s] = true;

    for (int i=1 ; i<=n ; i++) {
        if (!visit[i] && con[s][i]) {
            vCount += (dfs_visit(i,n));
        }
    }
    return vCount;
}

int dfs(int s, int n) {

    int vCount = 0;

    for (int i=1 ; i<=n ; i++) {
        visit[i] = false;
    }
    visit[s] = true;

    for (int i=1 ; i<=n ; i++) {
        if (!visit[i]) {
            vCount = dfs_visit(i,n);

            return vCount;
        }
    }
    return vCount;
}

int find_bridges(int n) {
    int aps = 0, i, j;


    for (int i=1  ; i<=n ; i++) {
        if (dfs(i,n) != (n-1)) aps++;
    }


    return aps;
}
char buf[10000];
int main( void ) {


    //freopen("inp.dat","r+",stdin);

    int n, result, vtx, plc;
    char *p;

    while (scanf("%d",&n)==1 && n!=0) {
        getchar();

        init_con(n);
        edges.clear();

        while (gets(buf)) {
            if (!strcmp(buf,"0")) break;
            p = strtok(buf," ");
            sscanf(p,"%d",&plc);

            while ((p=strtok(NULL," "))) {
                sscanf(p,"%d",&vtx);

                con[plc][vtx] = con[vtx][plc] = true;
                edges.push_back(make_pair(plc,vtx));
            }
        }

        result = find_bridges(n);

        cout << result << endl;
    }


    return 0;
}

[C++] Bellman Ford Implementation

Bellman-Ford is a Single Source Shortest Path (SSSP) detection algorithm. I implemented this one using a new kind of approach to coding (new for me). I used a nested class implementation. The whole BFord algorithm is packed with it's data structure in an object. The edges are also implemented using an internal class in the object. I never did nested class before this. Looks awesome.

#include <cstdio>
#include <vector>

#define INF (1<<31 - 1)
#define NIL -1

using namespace std;

class bford {
  
public:
  
  class edge {
  public:
 int u, v, w;
  };
  
  int nVertex;
  int *d, *p;
  vector<edge> elist;
  
  bford( ) {
 d = new int[0];
 p = new int[0];
 elist.clear();
  }
  
  bool function( int s, int nVertex ) {
 
 d = new int[(const int)nVertex+1];
 p = new int[(const int)nVertex+1];
 
 int i, j, w, u, v;
 // init_single_source( s ) {
 for (i=0 ; i<=nVertex ; i++) {
  d[i] = INF;
  p[i] = NIL;
 }
 d[s] = 0;
 // }
 
 for (i=0 ; i<nVertex-1 ; i++) {
  for ( j=0 ; j<elist.size() ; j++) {
   // relax( elist[j].u, elist[j].v, elist[j].w ) {
   u = elist[j].u;
   v = elist[j].v;
   w = elist[j].w;
   
   if (d[v] > d[u]+w) {
    d[v] = d[u]+w;
    p[v] = u;
   }
   // }
  }
 }
 
 for (i=0 ; i<elist.size() ; i++) {
  if ( d[ elist[i].v ] > d[ elist[i].u ] + elist[i].w ) {
   return false;
  }
 }
 return true;
  }

};

int main( void ) {
  
  int i, u, v, w, nVertex, nEdge;
  
  bford grp;
  scanf("%d",&nVertex);
  
  scanf("%d",&nEdge);
  
  for (i=0 ; i<nEdge ; i++) {
 scanf("%d %d %d",&u,&v,&w);
 grp.elist.push_back(bford::edge{u,v,w});
  }
  
  printf("%s\n",(grp.function( 1, nVertex )?"True":"False"));
  
  for (i=1 ; i<=nVertex ; i++) {
 printf("%d - %d\n",i, grp.d[i]);
  }
  
  
  return 0;
  
}

[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.
It's 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\n",pr[j]);  //|Last one can't have
}    //|can't 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("-----\n");
  
  for (i=1 ; i<=conn ; i++) {
   scanf("%d %d",&u, &v);
   if (bfs(u,v,n)) {
    print_path( v );
   } else {
    printf("connection impossible\n");
   }
  }
 }
}

[UVa] 532 - Dungeon Master

With this, I get inside the first 1000 coders on UVa. :)

Submission details:

Submission no: 9461491
Problem no: 532 
Problem title: Dungeon Master
Status: Accepted
Language: C++
Runtime: 0.012
Date of submission: 2011-11-11
Time of submission: 11:12:39

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <queue>
#define INF 9999999
using namespace std;

typedef struct xp
{
    int l, x, y;
} cord;

bool color[100][100][100];
int d[100][100][100];
char inp[100][100][100];

int dirs[10][4]={ {-1,0,0}, {1,0,0}, {0,-1,0}, {0,0,-1}, {0,0,1}, {0,1,0} };

int bfs(cord S, cord E, cord M)
{
    int i, j, k;

    for (i=0 ; i<=M.l+1 ; i++)
    {
        for (j=0 ; j<=M.x+1 ; j++)
        {
            for (k=0 ; k<=M.y+1 ; k++)
            {
                color[i][j][k]=false;
                d[i][j][k]=INF;
            }
        }
    }
    color[S.l][S.x][S.y]=true;
    d[S.l][S.x][S.y]=0;

    cord u, temp;

    queue<cord> q;
    q.push(S);
    while (!q.empty())
    {
        u = q.front();
        q.pop();

        for (i=0 ; i<6 ; i++)
        {
            temp.l = u.l+dirs[i][0];
            temp.x = u.x+dirs[i][1];
            temp.y = u.y+dirs[i][2];

            if (!color[temp.l][temp.x][temp.y] && inp[temp.l][temp.x][temp.y]!='#')
            {
                if (temp.l<1||temp.l>M.l||temp.x<1||temp.x>M.x||temp.y<1||temp.y>M.y)
                    continue;
                color[temp.l][temp.x][temp.y]=true;
                d[temp.l][temp.x][temp.y]=d[u.l][u.x][u.y]+1;
                if (i==E.l && j==E.x && k==E.y) return d[temp.l][temp.x][temp.y];
                    q.push(temp);
            }
        }
    }

    return d[E.l][E.x][E.y];
}


int main()
{
    int l, w, h, i, j, k, res;
    cord S, E, M;
    while (scanf("%d %d %d",&l,&h,&w)==3 && l&&h&&w)
    {
        getchar();

        M.l = l;
        M.x = h;
        M.y = w;

        for (i=1 ; i<=l ; i++)
        {
            for (j=1 ; j<=h ; j++)
            {
                gets(&inp[i][j][1]);
                for (k=1 ; k<=w ; k++)
                {
                    if (inp[i][j][k]=='S')
                    {
                        S.l = i;
                        S.x = j;
                        S.y = k;
                    }
                    if (inp[i][j][k]=='E')
                    {
                        E.l = i;
                        E.x = j;
                        E.y = k;
                    }
                }
            }
            gets(&inp[i][j][1]);
        }

        res = bfs(S,E,M);

        if (res==INF)
            printf("Trapped!\n");
        else
            printf("Escaped in %d minute(s).\n",res);
    }
    return 0;
}