今日ac题

【模板】拓扑排序 / 家谱树 - 洛谷

终于凭着仅存的记忆写出来了，虽然是板子题

#include 
#include 
#include 
using namespace std;
 
const int N = 1010;
int e[N], ne[N], h[N], idx;
int n, ind[N];
queue<int> q, ans;
 
void add(int a, int b)
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}
 
void topo()
{
    for(int i = 1; i <= n; i ++ )
    {
        if(!ind[i])
        {
            q.push(i);
        }
    }
    
    while(q.size())
    {
        int t = q.front();
        ans.push(t);
        q.pop();
        
        for(int i = h[t]; i != -1; i = ne[i])
        {
            int j = e[i];
            ind[j] --;
            if(!ind[j])
            {
                q.push(j);
            }
        }
    }
}
 
int main()
{
    cin >> n;
    
    memset(h, -1, sizeof h);
    for(int i = 1; i <= n; i ++ ) 
    {
        int x;
        while(cin >> x)
        {
            if(x == 0) break;
            else
            {
                add(i, x);
                ind[x] ++;
            }
        }
    }
    
    topo();
    
    while(ans.size())
    {
        cout << ans.front() << ' ';
        ans.pop();
    }
    return 0;
}

家谱 - 洛谷

也算是模板题吧，就是用map映射string数组

#include 
#include 
#include 
using namespace std;
 
map p;
 
string find(string x)
{
    if(x != p[x]) p[x] = find(p[x]);
    return p[x];
}
 
int main()
{
    char op;
    string a;
    while(cin >> op)
    {
        if(op == '$') break;
        else if(op == '#')
        {
            cin >> a;
            if(p[a] == "") p[a] = a;
        }
        else if(op == '+')
        {
            string b;
            cin >> b;
            p[b] = find(a);
        }
        else
        {
            string c;
            cin >> c;
            
            cout << c << ' ' << find(c) << endl;
        }
    }
    
    return 0;
}