专栏首页算法修养CodeForces #549 Div.2 C Queen

CodeForces #549 Div.2 C Queen

题目

水题,dfs

#include <iostream>
#include <stdio.h>
#include <algorithm>

using namespace std;

#define MAX 100000

struct Node
{
    int value;
    int c;
    int next;
}edge[MAX+5];
int pos;
int head[MAX+5];
int a[MAX+5];
int aa=0;
int n;
void Init()
{
    for(int i=1;i<=n;i++)
        head[i]=-1;
    pos=0;
}

void add(int x,int y,int c)
{
    edge[pos].value =y;
    edge[pos].c = c;
    edge[pos].next = head[x];
    head[x]=pos++;
}

void dfs(int root,int c)
{
    int x=head[root];
    
    int t=0;
    while(x!=-1)
    {
       if(!(c==1&&edge[x].c==1))
       {
           t=1;
       }
        
        dfs(edge[x].value,edge[x].c);
        x=edge[x].next;
    }
    
    if(t==0&&c==1)
        a[aa++]=root;
}

int main()
{
    scanf("%d",&n);
    Init();
    int p,c;
    int root=0;
    for(int i=1;i<=n;i++)
    {
        scanf("%d%d",&p,&c);
        if(p==-1)
        {
            root=i;
            continue;
        }
        add(p,i,c);
    }
    
    dfs(root,0);
    
    if(aa==0)
        printf("-1\n");
    else
    {
        sort(a,a+aa);
        for(int i=0;i<aa;i++)
        {
            if(i!=aa-1)
                printf("%d ",a[i]);
            else
                printf("%d\n",a[i]);
        }
    }
    return 0;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 天梯赛 大区赛 L3-014.周游世界 (Dijkstra)

    L3-014. 周游世界 时间限制 200 ms 内存限制 65536 kB 代码长度限制 8000 B 判题程序 Standar...

    ShenduCC
  • LeetCode 13 Roman to Integer

    ShenduCC
  • LeetCode Contest 166

    但是在用c++的快排的时候,被坑了,我一直的习惯是写自定义比较函数,没有写运算符重载,不知道为什么一直RE,浪费了挺多时间

    ShenduCC
  • 南京网络预选赛 The Preliminary Contest for ICPC Asia Nanjing 2019 H. Holy Grail 多源最短路

    用户2965768
  • Topcoder SRM 698 Div1 250 RepeatString(dp)

    attack
  • View的工作原理

    View的绘制流程是从ViewRoot的PerformTraversals方法开始的。它经过measure,layout,draw三个过程将view绘制出来。m...

    提莫队长
  • 洛谷P4383 [八省联考2018]林克卡特树lct(DP凸优化/wqs二分)

    小L 最近沉迷于塞尔达传说:荒野之息(The Legend of Zelda: Breath of The Wild)无法自拔,他尤其喜欢游戏中的迷你挑战。

    attack
  • LeetCode 593. 有效的正方形(数学)

    Michael阿明
  • 图论--LCA--树上倍增法(在线)

    风骨散人Chiam
  • 2038:[2009国家集训队]小Z的袜子(hose)

    用户2965768

扫码关注云+社区

领取腾讯云代金券