top of page

CCC 2001 S3 : Strategic Bombing


Solutions:

  1. Build a graph data structure, list1 keep one char's neighbor information. list2 keeps each edge that is two chars.

  2. for loop list2, firstly disconnect each edge neighborhood relationship, the do a DFS to look if can arrive from A to B, if it is true, the edge is a bridge that can bomb it, then place it to the result list. After that, connect the edge.

3. Print the result list.

def ishaltAB(list1):
    stacklist = []
    stacklist.append(0)
    visited = []
    for i in range(26):
        visited.append(0)
    visited[0] = 1
    while len(stacklist) > 0:
        n = stacklist.pop()
        for i in range(26):
            if list1[n][i] == 1 and visited[i] == 0:
                if i == 1:
                    return False
                else:
                    visited[i] = 1
                    stacklist.append(i)
    return True


list1 = []
list2 = []

for i in range(26):
    cur = []
    for j in range(26):
        cur.append(0)
    list1.append(cur)

while True:
    curs = input()
    if curs == '**':
        break
    list2.append(curs)
    n1 = ord(curs[0]) - ord('A')
    n2 = ord(curs[1]) - ord('A')
    list1[n1][n2] = 1
    list1[n2][n1] = 1
result = []
for x in list2:
    n1 = ord(x[0]) - ord('A')
    n2 = ord(x[1]) - ord('A')
    list1[n1][n2] = 0
    list1[n2][n1] = 0
    if ishaltAB(list1):
        result.append(x)
    list1[n1][n2] = 1
    list1[n2][n1] = 1

for x in result:
    print(x)

print("There are "+str(len(result))+" disconnecting roads.")

Recent Posts

See All

CCC '24 J5 - Harvest Waterloo

#include<iostream> #include <vector> #include <algorithm> #include <cmath> #include <stack> using namespace std; int main() { int r, c, sr, sc; cin >> r; cin >> c; int p[r][c]; bool v

CCC '24 J4 - Troublesome Keys

#include <iostream> #include <string> #include <map> #include <vector> #include <algorithm> #include <cmath> using namespace std; int main() { string ps; string ds; cin >> ps; cin >> ds;

CCC '22 J5 - Square Pool

#include<iostream> #include <vector> #include <algorithm> #include <cmath> using namespace std; bool rowcom(pair<int, int> a, pair<int, int> b){ return a.first < b.first; } bool colcom(pair<int,

Comments


bottom of page