1218. Episode Nth: The Jedi Tournament 夜

http://acm.timus.ru/problem.aspx?space=1&num=1218

缩点后形成树  树的根节点 就是有可能获胜的点

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<vector>
#include<map>
#include<cmath>
#include<queue>
#include<stack>
#include<algorithm>

#define LL long long
//#pragma comment(linker, "/STACK:1024000000,1024000000")

using namespace std;
const int INF=0x3f3f3f3f;
const int N=205;
struct node
{
    string name;
    int a[3];
}mem[N];
bool beat[N][N];
int low[N],dfn[N],deep;
bool in[N],visited[N],maybewin[N];
int f[N];
stack<int>St;
int n;
void Tarjan(int x)
{
    low[x]=dfn[x]=deep++;
    visited[x]=true;
    St.push(x);
    in[x]=true;
    for(int l=1;l<=n;++l)
    {
        if(beat[x][l]==false)
        continue;
        if(!visited[l])
        {
            Tarjan(l);
            low[x]=min(low[x],low[l]);
        }else if(in[l])
        {
            low[x]=min(low[x],dfn[l]);
        }
    }
    if(low[x]==dfn[x])
    {
        while(St.top()!=x)
        {
            f[St.top()]=x;
            in[St.top()]=false;
            St.pop();
        }
        f[St.top()]=x;
        in[St.top()]=false;
        St.pop();
    }
}
bool Kill(int i,int j)
{
    int k=0;
    for(int l=0;l<3;++l)
    if(mem[i].a[l]>mem[j].a[l])
    ++k;
    if(k>=2)
    return true;
    return false;
}
int main()
{
    //freopen("data.txt","r",stdin);
    while(cin>>n)
    {
        for(int i=1;i<=n;++i)
        {
            cin>>mem[i].name;
            for(int j=0;j<3;++j)
            cin>>mem[i].a[j];
        }
        memset(beat,false,sizeof(beat));
        for(int i=1;i<=n;++i)
        for(int j=1;j<=n;++j)
        if(Kill(i,j))
        beat[i][j]=true;
        memset(visited,false,sizeof(visited));
        for(int i=1;i<=n;++i)
        if(!visited[i])
        Tarjan(i);
        memset(maybewin,true,sizeof(maybewin));
        for(int i=1;i<=n;++i)
        {
            for(int j=1;j<=n;++j)
            if(beat[i][j]&&f[i]!=f[j])
            maybewin[f[j]]=false;
        }
        for(int i=1;i<=n;++i)
        {
            if(maybewin[f[i]])
            cout<<mem[i].name<<endl;
        }
    }
    return 0;
}