CF-Avito Code Challenge 2018-C-Useful Decomposition


ACM模版

描述

这里写图片描述
这里写图片描述

题解

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

所以,这个题也就是先找根,肯定只有根的 E [ i ] . s i z e ( ) > 2 ,遍历一遍查找,如果找到了不止一个根,那么输出 N o ,如果一个也没有找到,说明这是一个特殊的树,可以当做一条链看,将它的根置为 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;
}
智能推荐

注意!

本站转载的文章为个人学习借鉴使用,本站对版权不负任何法律责任。如果侵犯了您的隐私权益,请联系我们删除。



 
© 2014-2019 ITdaan.com 粤ICP备14056181号  

赞助商广告