求出每个点双连通分量，如果在一个点双连通分量中有奇环，则这个分量每个点都在一个奇环中。 关键是要知道怎么求点双连通分量以及点双连通的性质。
fzu2181 http://acm.fzu.edu.cn/problem.php?pid=2181
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
#define N 1100 int n,m,k;
int g[N][N];
int vis[N];
int height[N];
int stk[N];
int deep,top;
int mark[N];
int save[N]; //用来记录特殊状态
int ans; int dfs(int s,int num)
{
vis[s]=deep++;
stk[top++]=s;
height[s]=num;
int mi=vis[s];
for(int i=;i<=n;i++)
{
if(g[s][i]==) continue;
if(vis[i]==-) //这个点未被访问
{
dfs(i,num+);
if( vis[i]>=vis[s] )//表示这个圈与世无争,必须单独处理掉
{
//开始处理！
int cnt=;
int tcnt=;
int flag=;
while(stk[top-]!=s)
{
cnt++;
if(mark[stk[top-]]==) flag=;//表示这一堆有奇环
if(save[stk[top-]]==) tcnt++;
top--;
} if(flag==)//这一堆不存在奇环
{
save[s]=;
ans += cnt+-tcnt;
} }
else
{
mi = min(mi,vis[i]);
}
}
else
{
mi=min(mi,vis[i]);//找当前能到达最上方的点
if( (height[s]-height[i])%== )//表示当前点在一个奇环中
mark[s]=;
}
}
vis[s]=mi;
return vis[s];
} int main()
{
int T;
scanf("%d",&T);
while(T--)
{
scanf("%d%d%d",&n,&m,&k);
memset(g,,sizeof(g));
for(int i=;i<m;i++)
{
int x,y;
scanf("%d%d",&x,&y);
g[x][y]=g[y][x]=;
}
for(int i=;i<=n;i++)
for(int j=;j<=n;j++)
{
if(i==j) g[i][j]=;
else if(g[i][j]==) g[i][j]=;
else g[i][j]=;
}
//构建逆图
memset(vis,-,sizeof(vis));
memset(save,,sizeof(save));
memset(mark,,sizeof(mark));
deep=;
top=;
ans=;//表示有多少不能参与游戏
for(int i=;i<=n;i++)
{
if(vis[i]==-)
{
dfs(i,);
}
}
if(ans<k) printf("What a Pity.\n");
else printf("Let's Fire!\n");
}
return ;
}