k862. 輩份比較

        假設B,C是A的祖先，D,E是A的子孫,F是E的子孫，如果我們先忽略輩分這件事情，單純從A點走到F，那就是一個單純的BFS就可以解決的事情，只要在BFS的基礎上，讓每個節點記錄自己的父輩與子孫輩的成員即可。

下列附上程式碼：

class Node:
    def __init__(self):
        self.father = []
        self.child = []
        self.dis = -99999999


s = set()
n = int(input())
d = {}
for i in range(n):
    c,f = input().split()
    if c not in d:
        d[c] = Node()
    if f not in d:
        d[f] = Node()
    d[c].father.append(f)
    d[f].child.append(c)
    
start,target = input().split()

d[start].dis = 0
p = [start]
keep = True
while keep:
    for i in p:
        for j in d[i].father:
            if j not in s:
                s.add(j)
                d[j].dis = d[i].dis-1
                p.append(j)
                if j == target:
                    keep = False
                    break
        for j in d[i].child:
            if j not in s:
                s.add(j)
                d[j].dis = d[i].dis+1
                p.append(j)
                if j == target:
                    keep = False
                    break
        if keep == False: break
print(d[target].dis)

m702. 傑出校友票選活動

         題目要比對各個人名出現的次數，因為人名是字串，不方便直接用陣列做排序與索引，所以可以先放到map裡面去計次，記完之後再放回vector裡做排序即可。

#include <iostream>
#include <algorithm>
#include <map>
#include <vector>

using namespace std;

int main()
{
    cin.tie(0) , cin.sync_with_stdio(0);
    int n,m;
    cin >> n >> m;
    map<string , int> t;
    for(int i = 0; i < n; i++) {
        string s;
        cin >> s;
        t[s] += 1;
    }
    vector<pair<int , string>> v;
    for(auto it=t.begin(); it != t.end(); it++) {
        pair<int,string> p;
        p.first = it->second;
        p.second = it->first;
        v.push_back(p);
    }
    sort(v.begin() , v.end());
    for(int i = 0; i < m; i++) {
        cout << v[v.size()-1-i].second << " ";
    }
    cout << endl;

    return 0;
}