CF-Avito Code Challenge 2018-C-Useful Decomposition

ACM模版

描述

题解

题意弄懂了这个题就是很水的题，给定一个棵树，让你判断，它是否是放射状的，也就是说，这棵树是否是由一个根结点让外延伸了若干条链，并且每条链不能分叉；如果这个树不是放射状的，那么就 No$No$。

所以，这个题也就是先找根，肯定只有根的 E[i].size()>2$E[i].size()>2$，遍历一遍查找，如果找到了不止一个根，那么输出 No$No$，如果一个也没有找到，说明这是一个特殊的树，可以当做一条链看，将它的根置为 1$1$ 就可以了，然后从根开始找每条链的终点，输出根和终点即可。

代码

#include <cstdio>
#include <iostream>
#include <vector>

using namespace std;

const int MAXN = 1e5 + 10;

int n;
int vis[MAXN];
vector<int> E[MAXN];

void dfs(int u, int pre)
{
    if (E[u].size() == 1)
    {
        printf("%d\n", u);
        return ;
    }

    for (int i = 0; i < E[u].size(); i++)
    {
        if (E[u][i] != pre)
        {
            dfs(E[u][i], u);
        }
    }
}

int main(int argc, const char * argv[])
{
    cin >> n;

    int u, v;
    for (int i = 1; i < n; i++)
    {
        scanf("%d%d", &u, &v);
        E[u].push_back(v);
        E[v].push_back(u);
    }

    int rt = 0, flag = 1;
    for (int i = 1; i <= n; i++)
    {
        if (E[i].size() > 2 && rt == 0)
        {
            rt = i;
        }
        else if (E[i].size() > 2)
        {
            flag = 0;
            break;
        }
    }

    if (!flag)
    {
        cout << "No\n";
    }
    else
    {
        cout << "Yes\n";

        if (rt == 0)
        {
            rt = 1;
        }

        printf("%d\n", (int)E[rt].size());
        for (int i = 0; i < E[rt].size(); i++)
        {
            printf("%d ", rt);
            dfs(E[rt][i], rt);
        }
    }

    return 0;
}