If start from all the leaf airport that from one airport could win, start from this airport suerly will lose. Otherwise,he could win.

May be test 10 is something like

3 2
1 2
2 3
First player loses

The start airport just has one airport connected.

my code is wrong in the test 8 but i dont know the test, can you help me?

Edited by author 11.07.2015 20:44

ok, now I have AC :)


Edited by author 29.06.2009 17:03

1. If we regard the start airport as the root,it is clear that the graph is a tree.
2. If start from all the leaf airport that from one airport could win, start from this airport suerly will lose. Otherwise,he could win.
3. We use a flag to record start from one airport will win or not.Just DFS to obtain all flag.
In this way,you could get AC in O(e).
Is there any better way to solve this problem?
I think the answer is yes.
So,could you write down your thought?

I submited several times and i got WA at test #8.
I really appreciate if you would be so kind by giving me test #8.
Thank you.

Edited by author 30.09.2005 16:11

Edited by author 30.09.2005 16:11

I got WA#3 and can't anderstand why...



Edited by author 08.04.2005 22:01

Edited by author 08.04.2012 20:51

#include <cstdio>
#include <vector>
#include <algorithm>

using namespace std;

vector < vector < int > > g;
vector < bool > d;

void dfs(int v, int p = -1)
{
    if ((int)g[v].size()==1) d[v]=false;
    d[v] = false;
    for (int i = (int)g[v].size()-1; i >= 0; i--)
    {
        int to = g[v][i];
        if (to == p) continue;
        dfs(to,v);
        if (!d[to]) d[v] = true;
    }
}

int main() {
    int n,root;
    scanf("%d%d",&n,&root);
    g.resize(n+1); d.resize(n+1);
    for (int i=1;i<=n-1;i++)
    {
        int u,v; scanf("%d%d",&u,&v);
        g[u].push_back(v);
        g[v].push_back(u);
    }
    for (int i=1;i<=n;i++)
        sort(g[i].begin(),g[i].end());

    dfs(root);
    if (d[root])
    {
        for (int i = 0; i<(int)g[root].size(); i++)
            if (!d[g[root][i]]) { printf("First player wins flying to airport %d",g[root][i]); return 0;}
    }
    puts("First player loses");
    return 0;
}

Could anybody give me the input data? I have no idea what's wrong with my program.

Sample Input
4 3
3 2
3 1
1 4

Sample Output
First player wins flying to airport 2

Hello! My solution got accepted, but now as I thought it through it is wrong. Here are some tests that will fail me:
Test 1:
6 3
1 2
2 3
4 5
5 6
6 3
Answer:
First player wins flying to airport 6
Test 2:
15 12
1 2
2 3
4 5
5 6
6 3
3 11
7 8
8 9
9 10
10 11
11 12
13 12
14 13
15 14
Answer:
First player wins flying to airport 11

Edited by author 09.05.2009 13:47

Edited by author 23.02.2009 21:22

#include<stdio.h>
#include<stdlib.h>
#define MAX 1002
int join[MAX][MAX],cont[MAX],used[MAX],win[MAX];
int np,mark,fri;
int tree(int aa)
{
    int i,j,k,mar=0,min1=MAX,min2=MAX;
    used[aa]=1;
    if(cont[aa]==1&&aa!=fri)//!!cout为1可为终点，亦可为起点~！！
    {
       win[aa]=aa;
        return 0;
    }
    for(i=1;i<=np;i++)
    {
        if(join[aa][i]&&!used[i])
        {

            k=tree(i);
            if(!k&&min1>win[i])
            {
                mar=1;
                min1=win[i];
            }
            if(k&&min2>win[i])
                min2=win[i];
        }
    }
    if(mar)
    {
        win[aa]=min1;
            return 1;
    }
    else
    {
        win[aa]=min2;
        return 0;
    }
}

int main()
{
    int i,j,k,mar=0;
    scanf("%d%d",&np,&fri);
    for(i=1;i<np;i++)
    {
        scanf("%d%d",&j,&k);
        join[j][k]=1;
        join[k][j]=1;
        cont[j]++;
        cont[k]++;
    }
    k=tree(fri);
    if(k)printf("First player wins flying to airport %d\n",win[fri]);
    else printf("First player loses\n");
//    system("pause");
    return 0;
}

Thx in advance!

I don't know why I got WA

Edited by author 27.12.2006 20:22

I suspect there is something redundance after this test case, i.e, there is more than N-1 lines after the first line.

Due to memory requirements I used std::vector<bool> arrays for
storing node edges, but it chashes!
(function std::vector<bool>::operator[](int), to be exact)

Does anybody knows why?

P.S. If I use, f.e., std::bitset<> instead, I get strong AC.
Therefore, timus's std::vector<bool> has error, hasnt it?