CCC 2000 S3 or J5:Surfin

https://www.cemc.uwaterloo.ca/contests/computing/2000/stage1/2000CCCStage1Contest.pdf

Solution:

1. Build a map to store each page URL information, the key is the page's URL, the value is an array that stores the page's URL link.

2. Use a DFS to find if two pair URL is connection.

Python :

def isreach(result, s, d):
    if s not in result:
        return False
    statcklist = []
    visited = []
    statcklist.append(s)
    visited.append(s)
    while len(statcklist) > 0:
        cur = statcklist.pop()
        for x in result[cur]:
            if x == d:
                return True
            if x not in visited:
                statcklist.append(x)
                visited.append(x)
    return False


N = int(input())
result = {}
for i in range(N):
    sw = input()
    list2 = []
    cur = ""
    while cur != "</HTML>":
        cur = input()
        npos = cur.find("A HREF")
        while npos != -1:
            epos = npos + 8
            while cur[epos] != '"':
                epos += 1
            list2.append(cur[npos+8:epos])
            cur = cur[epos:]
            npos = cur.find("A HREF")
    result[sw] = list2

listsource = []
listend = []
while True:
    cur1 = input()
    if cur1 == "The End":
        break
    listsource.append(cur1)
    listend.append(input())

for x in result:
    for i in range(len(result[x])):
        print("Link from " + x + " to " + result[x][i])

for i in range(len(listsource)):
    if isreach(result, listsource[i], listend[i]):
        print("Can surf from " + listsource[i] + " to "+ listend[i]+".")
    else:
        print("Can't surf from " + listsource[i] + " to "+ listend[i]+".")

c++ solution:

#include <iostream>
#include <map>
#include <vector>
#include <set>
using namespace std;
map<string, vector<string>> link;
void dfs(string start, string end){
   vector<string> mystack;
   set<string> visited;
    mystack.push_back(start);
    visited.insert(start);
    while(mystack.size() > 0){
       string cur = mystack.back();
       mystack.pop_back();
       if(cur == end){
          cout<<"Can surf from " + start + " to " + end + "."<<endl;
          return;
       }
       if(link.find(cur) == link.end()){
          continue;
       }
       for(unsigned int i = 0; i < link[cur].size(); i++){
          if(visited.find(link[cur][i]) == visited.end()){
             mystack.push_back(link[cur][i]);
             visited.insert(link[cur][i]);
          }
       }

    }
    cout<<"Can't surf from " + start + " to " + end + "."<<endl;
}
int main() {
  int numURLs;
  string tempURL;
  int n = 1;
  int i = 0;
  string x;
  int x1;
  cin >> numURLs;
  while(i < numURLs) {
   string mkey;
    cin >> mkey;
    link[mkey] = vector<string>();
    cin >> x;
    while(x != "</HTML>") {

      if (x.find("HREF") != string::npos) {
        tempURL = x;

        x1 = x.find(">") - 7;
        //cout<<x.find(">")<<endl;
        //cout<<x<<"     "<<x1<<endl;
        tempURL = tempURL.substr(6, x1);
        link[mkey].push_back(tempURL);
        cout << "Link from " << mkey << " to " << tempURL << "\n";

        n++;
      }
      cin >> x;
    }
    n = 1;
    i++;
  }

  string start;
  string end;

  while(end != "End") {
     cin >> start;
     cin >> end;
     if(end == "End") {
        break;
     }
      dfs(start, end);
  }
}