PTA甲级

1118 Birds in Forest

#include<iostream>
#include<vector>
#include<set>
#include<algorithm>

using namespace std;

const int N = 1e4 + 10;
int n , p[N];
set<int>se , st;
int bird;

int find(int x)
{
    if(p[x] != x) p[x] = find(p[x]);
    return p[x];
}

int main()
{
    cin >> n;
    for(int i = 1;i < N;i ++) p[i] = i;
    for(int i = 0;i < n;i ++)
    {
        int k;
        cin >> k;
        int last = -1;
        for(int j = 0;j < k;j ++)
        {
            if(!j) cin >> last;
            else 
            {
                int x;
                cin >> x;
                int fa = find(x) , fb = find(last);
                if(fa != fb) p[fa] = fb;
                last = x;
            }
            st.insert(last);
            bird = max(bird , last);
        }
    }
    for(int i : st)
        se.insert(find(i));
    cout << se.size() << " " << bird << endl;
    cin >> n;
    while(n --)
    {
        int x , y;
        cin >> x >> y;
        if(find(x) == find(y)) puts("Yes");
        else puts("No");
    }
    return 0;
}

1119 Pre- and Post-order Traversals

使用字符串作为答案进行枚举更为简单

#include<iostream>
#include<cstring>
#include<vector>

using namespace std;

const int N = 100;
int n;
int pre[N] , post[N];

int build(int pr , int pl , int tr , int tl , string &res)
{
    if(pr > pl) return 1; // 建完方案数+1
    if(pre[pr] != post[tl]) return 0;
    int root = pre[pr];
    int cnt = 0;
    for(int i = pr;i <= pl;i ++)
    {
        string lv , rv;
        int l = build(pr + 1 , i , tr , tr + i - pr - 1 , lv);
        int r = build(i + 1 , pl , tl - pl + i , tl - 1 , rv);
        if(l && r) // 左右都建完
        {
            res = lv + to_string(root) + " " + rv;
            cnt += l * r;
            if(cnt > 1) break;
        }
    }
    return cnt;
}


int main()
{
    cin >> n;
    for(int i = 0;i < n;i ++) cin >> pre[i];
    for(int i = 0;i < n;i ++) cin >> post[i];
    string res;
    int cnt = build(0 , n - 1 , 0 , n - 1 , res);
    if(cnt == 1) puts("Yes");
    else puts("No");
    res.pop_back();
    cout << res << endl;
    return 0;
}

1122 Hamiltonian Cycle

#include<iostream>
#include<vector>
#include<set>

using namespace std;

const int N = 210 , M = 1e5 + 10;
int n , m;
bool g[N][N];

bool check(vector<int>&v , int k)
{
    if(v[0] != v[k - 1]) return false; // 保证是一个环
    set<int>se;
    for(int i = 0;i < k;i ++)
        se.insert(v[i]);
    if(se.size() != n) return false;
    for(int i = 1;i <= n;i ++)
        if(!se.count(i)) return false;
    for(int i = 1;i < k;i ++)
        if(!g[v[i]][v[i - 1]] && !g[v[i - 1]][v[i]]) return false;
    return true;
}

int main()
{
    cin >> n >> m;
    for(int i = 0;i < m;i ++)
    {
        int a , b;
        cin >> a >> b;
        g[a][b] = g[b][a] = true;
    }
    cin >> m;
    while(m --)
    {
        vector<int>v(M);
        int k;
        cin >> k;
        for(int i = 0;i < k;i ++)
            cin >> v[i];
        if(check(v , k) && k - 1 == n) puts("YES");
        else puts("NO");
    }
    return 0;
}

1126 Eulerian Path

注意图有可能是非联通的

#include<iostream>

using namespace std;

const int N = 510;
int n , m;
int in[N];
bool st[N] , g[N][N];

void dfs(int u)
{
    st[u] = true;
    for(int i = 1;i <= n;i ++)
        if(!st[i] && g[u][i]) dfs(i);
}


void euler()
{
    int cnt = 0;
    bool f = true;
    for(int i = 1;i <= n;i ++)
    {
        if(!st[i]) f = false;
        if(i == 1) cout << in[i];
        else cout << " " << in[i];
        if(in[i] & 1) cnt ++;
    }
    cout << endl;
    if(cnt == 0 && f) puts("Eulerian");
    else if(cnt == 2 && f) puts("Semi-Eulerian");
    else puts("Non-Eulerian");
}

int main()
{
    cin >> n >> m;
    while(m --)
    {
        int a , b;
        cin >> a >> b;
        g[a][b] = g[b][a] = true;
        in[a] ++ , in[b] ++;
    }
    dfs(1); // 有可能是非连通图
    euler();
    return 0;
}