1242. Werewolf

2956 단어 ol
http://acm.timus.ru/problem.aspx?space=1&num=1242
단순 dfs  데 이 터 를 문자열 에서 추출 해 야 합 니 다. (문자열 의 빈 칸 은 임의의 위치 에 있 습 니 다)
#include<iostream>

#include<cstdio>

#include<cstring>

#include<string>

#include<vector>

#include<map>

#include<queue>

#include<stack>

#include<algorithm>



using namespace std;

const int INF=0x3f3f3f3f;

const int N=1005;

int head1[N],I1;

int head2[N],I2;

struct node

{

    int j,next;

}side1[N*100],side2[N*100];

bool werewoof[N];

int ans[N];

void Add1(int i,int j)

{//cout<<i<<" "<<j<<endl;

    side1[I1].j=j;

    side1[I1].next=head1[i];

    head1[i]=I1++;

}

void Add2(int i,int j)

{

    side2[I2].j=j;

    side2[I2].next=head2[i];

    head2[i]=I2++;

}

void dfs1(int x)

{

    werewoof[x]=false;

    for(int t=head1[x];t!=-1;t=side1[t].next)

    {//cout<<x<<" "<<side1[t].j<<" "<<t<<endl;

        dfs1(side1[t].j);

    }

}

void dfs2(int x)

{

    werewoof[x]=false;

    for(int t=head2[x];t!=-1;t=side2[t].next)

    {

        dfs2(side2[t].j);

    }

}

bool Findrelative(int &l1,int &l2,char stmp[])

{

    l1=0;

    int i=0;

    while(stmp[i]==' ')

    ++i;

    if(stmp[i]=='B')

    return false;

    for(;stmp[i]!='\0';++i)

    {

        if(stmp[i]>'9'||stmp[i]<'0')

        break;

        l1=l1*10+stmp[i]-'0';

    }

    l2=0;

    while(stmp[i]==' ')

    ++i;

    for(;stmp[i]!='\0';++i)

    {

        if(stmp[i]>'9'||stmp[i]<'0')

        break;

        l2=l2*10+stmp[i]-'0';

    }

    return true;

}

int main()

{

    //freopen("data.txt","r",stdin);

    int n;

    while(scanf("%d",&n)!=EOF)

    {

        getchar();

        memset(head1,-1,sizeof(head1));

        memset(head2,-1,sizeof(head2));

        I1=I2=0;

        char stmp[100];

        while(gets(stmp))

        {

            int l1,l2;

            if(!Findrelative(l1,l2,stmp))

            break;

            Add1(l1,l2);

            Add2(l2,l1);

        }

        memset(werewoof,true,sizeof(werewoof));

        int k;

        while(scanf("%d",&k)!=EOF)

        {

            dfs1(k);

            dfs2(k);

        }

        int m=0;

        for(int i=1;i<=n;++i)

        if(werewoof[i]==true)

        ans[m++]=i;

        if(m==0)

        printf("0
"); else { for(int i=0;i<m;++i) { if(i) printf(" "); printf("%d",ans[i]); } printf("
"); } } return 0; }

좋은 웹페이지 즐겨찾기