题目解析

给出 $n$ 以及 $n$个问题的五个选项（可能会重复！）以及考生给出的答案。考生的答案表明，他喜欢这个答案更甚于其余答案。你的任务是将答案分成尽可能少的组，使得组内的答案互相冲突，即他同时喜欢某个答案甚于另一个答案同时喜欢另一个答案甚于该答案。

解题思路

如果将喜欢和甚于和建边联系起来，那么这题就是一个标准的强连通分量板子。 该题所有的坑点，都在答案字典序与多测不清空的基础上。

#include <iostream>
#include <vector>
#include <stack>
#include <cstring>
#include <algorithm>
#include <map>
using namespace std;
int n,dft,cscc,dfn[30],low[30],vis[30],ins[30],blt[30],mxs;
vector<int> edgs[30];
vector<char> ans[30];
stack<int> stck;
map<char,int> gid;
map<int,char> gch;
void dfs(int u)
{
    low[u]=dfn[u]=++dft;
    vis[u]=true;
    stck.push(u),ins[u]=true;
    for(auto v:edgs[u]){
        if(!vis[v]) dfs(v),low[u]=min(low[u],low[v]);
        else if(ins[v]) low[u]=min(low[u],dfn[v]);
    }
    if(dfn[u]==low[u]){
        ++cscc;
        while(!stck.empty()){
            int x=stck.top();stck.pop();
            blt[x]=cscc;
            ins[x]=false;
            if(x==u) break;
        }
    }
}
void tarjan()
{
    for(int i=1;i<=cscc;i++) ans[i].clear();
    dft=cscc=0;
    memset(dfn,0,sizeof dfn);
    memset(low,0,sizeof low);
    memset(vis,0,sizeof vis);
    memset(ins,0,sizeof ins);
    memset(blt,0,sizeof blt);
    while(!stck.empty()) stck.pop();
    for(int i=1;i<=mxs;i++) if(!vis[i]) dfs(i);
    for(int i=1;i<=mxs;i++) ans[blt[i]].push_back(gch[i]);
    for(int i=1;i<=cscc;i++) sort(ans[i].begin(),ans[i].end());
}
int main()
{
    bool outed=false;
    while(cin>>n&&n!=0){
        if(outed) cout<<endl;
        mxs=0;
        gid.clear(),gch.clear();
        for(int i=1;i<=29;i++) edgs[i].clear();
        for(int i=1;i<=n;i++){
            char a[6],ans;
            for(int i=1;i<=5;i++){
                cin>>a[i];
                if(!gid.count(a[i])) gid[a[i]]=++mxs,gch[gid[a[i]]]=a[i];
            }
            cin>>ans;
            for(int i=1;i<=5;i++)
                if(ans!=a[i]) edgs[gid[ans]].push_back(gid[a[i]]);
        }
        tarjan();
        sort(ans+1,ans+cscc+1);
        for(int i=1;i<=cscc;i++){
            bool oted=false;
            for(auto it:ans[i]){
                if(oted) cout<<" ";
                cout<<it;
                oted=true;
            }
            cout<<endl;
        }
        outed=true;
    }
    return 0;
}