#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iomanip>
#include <algorithm>
#include <vector>
#include <deque>
#include <limits>
#include <string>
#include <sstream>
using namespace std;

const int oo_min=0xcfcfcfcf,oo_max=0x3f3f3f3f;

int n,m,p;
vector<int> del;
vector<int> pre;
vector<vector<int> > a;
deque<int> q;

int bfs_1(int s)
{
    pre.resize(0);
    pre.resize(n+1,-1);
    pre[s]=0;
    q.resize(0);
    for (q.push_back(s);!q.empty();q.pop_front())
    {
        int now=q.front();
        for (int i=1;i<a[now].size();i++)
            if (del[a[now][i]]==0)
                if (pre[a[now][i]]!=pre[now])
                {
                    if (pre[a[now][i]]==-1)
                    {
                        pre[a[now][i]]=((pre[now])?0:1);
                        q.push_back(a[now][i]);
                    }
                }
                else
                    return 0;
    }
    return 1;
}

int main()
{
    while (~scanf("%d%d%d",&n,&m,&p))
    {
        del.resize(0);
        del.resize(n+1,0);
        a.resize(0);
        a.resize(n+1);
        for (int i=1;i<=n;i++)
            a[i].resize(1,0);
        for (int i=1;i<=m;i++)
        {
            int x,y;
            scanf("%d%d",&x,&y);
            a[x].push_back(y);
            a[y].push_back(x);
        }
        for (int i=1;i<=p;i++)
        {
            int d;
            scanf("%d",&d);
            del[d]=1;
            for (int i=1;i<=n;i++)
                if (del[i]==0)
                {
                    if (bfs_1(i)==1)
                        printf("Poor Fat Tour.\n");
                    else
                        printf("The Graph has Fat Tour.\n");
                    break;
                }
        }
    }
}

……数组开大……原来数组开小也会导致tle……

废话就是特别多的

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

秒杀 ~~

直接暴力O（n^3） + 利用答案的单调性 = AC

我觉得题目实在描述不清楚:

Vi1,Vi2,Vi3…Vik 其中Vi1=Vik ，如果k是奇数……

这样容易让人理解为这个环上的点是偶数个

题目的意思是说 这个环上有奇数个点

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

var

g :array[0..800,0..800]of integer;

a,f :array[0..800]of integer;

i,j,n,m,p,x,y :longint;

can,visit :array[0..800]of boolean;

function dfs(k,s:longint):boolean;

var

i :longint;

begin

for i:=1 to g[k,0] do

if can[g[k,i]] then

if not visit[g[k,i]] then

begin

visit[g[k,i]]:=true;

f[g[k,i]]:=s;

if dfs(g[k,i],s+1) then exit(true);

end

else

if (f[k]-f[g[k,i]])and 1=0 then exit(true);

exit(false);

end;

begin

read(n,m,p);

fillchar(g,sizeof(g),0);

for i:=1 to m do

begin

read(x,y);

inc(g[x,0]);

g[x,g[x,0]]:=y;

inc(g[y,0]);

g[y,g[y,0]]:=x;

end;

for i:=1 to p do read(a[i]);

fillchar(can,sizeof(can),true);

for i:=1 to p do

begin

can[a[i]]:=false;

fillchar(visit,sizeof(visit),false);

if dfs(1,1) then writeln('The Graph has Fat Tour.')

else

begin

writeln('Poor Fat Tour.');

break;

end;

end;

for j:=i+1 to p do writeln('Poor Fat Tour.');

end.

题目的意思就是要你判断当前的图中是否存在长度为奇数的环，也就是判断是不是不是一个二分图，可以用染色法，如果有矛盾，说明有奇数环。

p.s. 关于jlhs，我猜想是Jin Ling High School吧……还有为什么现在Vijos没几个nfls的人……

这就是个并查集的题,有个添加关系的顺序,问你添加到第几个关系的时候出现了矛盾.

然后输出一大堆The Graph has Fat Tour.,再输出一大堆Poor Fat Tour.

我也真够2的,第一次把调试信息给输出了,第二次的时候发现如果全都应该输出poor的时候比正确的多输出了一次=.=

我晕。一句话后面有个句号。居然没看到。

染色法,赞一个!

DFS+邻接矩阵也一遍AC

爽哉

O(E)

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

居然一次A.- -|

BFS.如果形成回路再判断是否合法就可以了..

如果当前没回路,那么后面肯定没有回路!!

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 1117ms

├ 测试数据 10：答案正确... 727ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：1844ms

居然邻接矩阵就AC了。。。。

奇偶点染色即可。。。感谢tyt神牛给予的启发

弱弱的问一句,jlhs是什么

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

yxc啊......

还记得我么...

LX胡说，这是无向图。。

谁冒充我？？？

LX赶快闪，保持JLHS队形。。。

回楼下，谁说无向图不能拓扑？

但是这道题的确不能拓扑

是jlhs's 小胖--wytf

题目很简单，不会的请看算法导论......

此小胖非彼小胖乃王小胖也。。。