14189: 【原4189】西部世界

题目

题目描述

author: DS TA 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/4189

Description

西部世界中有$N$个小镇, 小镇编号为1至$N$, 可以把西部世界的地图看成是一棵树, $N-1$条双向道路连接$N$个小镇, 满足任意两个小镇可以互相到达. 机器人中的领袖Dolores Abernathy觉醒了, 她打算揭竿起义,反抗人类. Dolores计划攻占一个小镇, 攻占某个小镇$u$后可以视为 去掉所有连接$u$的道路, 则剩下的$N-1$个小镇将分成若干个连通块, 为了让这场战役走向胜利, 她认为连通块规模最大的小镇数目应小于等于$N/2$. 身为觉醒机器人中的西部牛仔, 你来告诉她可以攻占的小镇有哪些.

Input Format

第一行包含一个正整数$N$,表示小镇的个数. 接下来$N-1$行,每行两个整数$u$, $v$表示一条道路 连接小镇$u$和小镇$v$.

Output Format

输出若干行,每行一个整数,表示可以攻占的小镇, 要求以升序顺序输出.

Sample Input

8 1 2 1 3 2 4 2 5 3 6 3 7 4 8

Sample Output

1 2

ligongzzz's solution

#include <iostream>
#include <vector>
using namespace std;

class node {
public:
    int parent = 0, child_num = 0;
    vector<int> child;
};

vector<node> tree_data;

int dfs(int root) {
    tree_data[root].child_num = 1;
    for (auto p : tree_data[root].child) {
        if (p != tree_data[root].parent) {
            tree_data[p].parent = root;
            tree_data[root].child_num += dfs(p);
        }
    }
    return tree_data[root].child_num;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int n;
    cin >> n;

    tree_data.resize(n + 1);

    for (int i = 0; i < n - 1; ++i) {
        int u, v;
        cin >> u >> v;
        tree_data[u].child.push_back(v);
        tree_data[v].child.push_back(u);
    }

    dfs(1);

    for (int i = 1; i <= n; ++i) {
        if (n - tree_data[i].child_num > n / 2) {
            continue;
        }
        bool flag = true;
        for (auto p : tree_data[i].child) {
            if (p != tree_data[i].parent) {
                if (tree_data[p].child_num > n / 2) {
                    flag = false;
                    break;
                }
            }
        }
        if (flag) {
            cout << i << " ";
        }
    }

    return 0;
}

Neight99's solution

#include <iostream>

using namespace std;

const int maxN = 1e5 + 100;

struct Node {
    int data;
    Node *next;

    Node(int d = 0, Node *n = 0) : data(d), next(n) {}
};

Node son[maxN] = {0};
int father[maxN] = {0}, Size[maxN] = {0}, ans[maxN] = {};
bool isNode[maxN] = {0};

int DFS(int, int);

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int N, k = 0, root;
    cin >> N;
    for (int i = 1; i < N; i++) {
        int u, v;
        cin >> u >> v;
        son[u].data = u;
        son[v].data = v;
        ans[u] = ans[v] = 1;
        if ((!isNode[u] && !isNode[v]) || (isNode[u] && !isNode[v])) {
            Node *p = &(son[u]);
            while (p->next != NULL) {
                p = p->next;
            }
            p->next = new Node(v);
            father[v] = u;
            isNode[u] = isNode[v] = 1;
        } else if (isNode[v] && isNode[u]) {
            Node *p = &son[v];
            while (p->next != NULL) {
                p = p->next;
            }
            p->next = new Node(u);
            father[u] = v;
            isNode[u] = isNode[v] = 1;
        }
    }

    for (int i = 1; i <= N; i++) {
        if (father[i] == 0) {
            root = i;
            break;
        }
    }

    DFS(root, N);

    for (int i = 1; i <= N; i++) {
        bool flag = 1;
        Node *p = &son[i];
        while (p->next != NULL) {
            p = p->next;
            if (Size[p->data] > N / 2) {
                flag = 0;
                break;
            }
        }
        if (N - Size[i] - 1 > N / 2) {
            flag = 0;
        }
        if (flag) {
            ans[k] = i;
            k++;
        }
    }

    for (int i = 0; i < k; i++) {
        cout << ans[i] << '\n';
    }

    return 0;
}

int DFS(int x, int N) {
    if (son[x].next == NULL) {
        return 1;
    } else {
        Node *p = &(son[x]);
        while (p->next != NULL) {
            p = p->next;
            Size[x] += DFS(p->data, N);
        }
        return Size[x] + 1;
    }
}

q4x3's solution

/**
 * dfs
 * 不能用vector真是太烦了
 * TAT
 **/
#include <iostream>

using namespace std;

int map[100233][100], sonnum[100233];
int N, tmp1, tmp2, siz[100233], vis[100233];

int dfs(int rt) {
    siz[rt] = 1;
    vis[rt] = 1;
    for(int i = 1;i <= sonnum[rt];++ i) {
        if(! vis[map[rt][i]]) {
            siz[rt] += dfs(map[rt][i]);
        }
    }
    return siz[rt];
}

bool check(int num) {
    if(N - siz[num] > (N >> 1)) return 0;
    for(int i = 1;i <= sonnum[num];++ i) {
        if(siz[map[num][i]] < siz[num] && siz[map[num][i]] > (N >> 1)) return 0;
    }
    return 1;
}

int main() {
    scanf("%d", &N);
    for(int i = 0;i < N - 1;++ i) {
        scanf("%d%d", &tmp1, &tmp2);
        map[tmp1][++ sonnum[tmp1]] = tmp2;
        map[tmp2][++ sonnum[tmp2]] = tmp1;
    }
    dfs(1);
    for(int i = 1;i <= N;++ i) {
        if(check(i)) printf("%d ", i);
    }
    printf("\n");
    return 0;
}

victrid's solution

#include <cstdio>
#include <iostream>
using namespace std;
struct ln {
    int pos;
    ln* next;
};

ln lis[1000005];
int sz[1000005]     = {0};
int parent[1000005] = {0};

int DFS(int pos) {
    sz[pos] = 1;
    ln* nx  = &lis[pos];
    while (nx->next != NULL) {
        nx = nx->next;
        if (parent[pos] != nx->pos) {
            parent[nx->pos] = pos;
            sz[pos] += DFS(nx->pos);
        }
    }
    return sz[pos];
}

int main() {
    int N, p, q;
    scanf("%d", &N);
    for (int i = 1; i < N; i++) {
        scanf("%d%d", &p, &q);
        lis[p].pos = p;
        lis[q].pos = q;
        ln* pp     = &lis[p];
        while (pp->next != nullptr) {
            pp = pp->next;
        }
        pp->next = new ln{q, nullptr};
        ln* qp   = &lis[q];
        while (qp->next != nullptr) {
            qp = qp->next;
        }
        qp->next = new ln{p, nullptr};
    }
    DFS(1);
    //Only one needed. I'm blind.
    for (int i = 1; i <= N; ++i) {
        if (N - sz[i] > N / 2) {
            continue;
        }
        bool flag = true;
        ln* nx    = &lis[i];
        while (nx->next != NULL) {
            nx = nx->next;
            if (parent[i] != nx->pos) {
                if (sz[nx->pos] > N / 2) {
                    flag = false;
                    break;
                }
            }
        }
        if (flag) {
            printf("%d ", i);
        }
    }
    return 0;
}