[POI 11 Stage 2]The Tournament

題目連結

我們先看看怎麼在時間內找出一個會贏的人

入度為$0$的點嗎？不是，如果整張圖是一個環就GG了
入度為$0$的$SCC$ ($Strongly\ Connected\ Component$) 嗎？
對了，就是它！

可以發現，位於同一個$SCC$內的點，不是全部有可能當冠軍，就是全部不可能當冠軍
因此，我們只須找出哪些$SCC$有可能直接或間接打敗所有其他$SCC$

先不管時間複雜度，我們來構造一個算法找出所有答案
先讓那些入度為$0$的$SCC$加入$queue$裡面，並標記為答案
然後，每次從$queue$弄出一個可能當冠軍的$SCC$ (稱作$u$)
枚舉還沒被標記答案的$SCC$ (稱作$nxt$)，只要發現$nxt$可以打敗$u$ (換句話說，$(從u連到nxt的邊數)<(u的大小)*(nxt的大小)$，也就是$u$無法壓倒性勝利$nxt$)，那麼$nxt$也可以當冠軍了！
把所有變成新冠軍的$SCC$加入$queue$裡面，並標記為答案

於是我們有了一個$O(N^{2})$的作法
真的是$O(N^{2})$嗎？

跟你說，如果你把還沒被標記答案的$SCC$用$set$來維護
傳上去就$AC$了

然後就會想問為甚麼
為甚麼？

可以發現，在枚舉還沒被標記答案的$SCC$時，只有兩種情況：
1. 當冠軍，從$set$中移除並加入$queue$
2. 被壓倒性勝利惹QAQ，繼續待在$set$裡面

時間複雜度取決於情況2.會發生多少次
可以發現，情況2.發生的次數不會超過圖上邊的數量 (想一想，為甚麼XD) (提示：要壓倒性勝利代表至少有一條從$u$連向$nxt$的邊)

時間複雜度：$O((N+M)+(N\log N+M))$ ($M$是邊數)

code:

#include<cstdio>
#include<cassert>
#include<vector>
#include<stack>
#include<algorithm>
#include<queue>
#include<set>
using namespace std;
void getmin(int &a,const int b){if(b<a)a=b;}
vector<int>ET[100000];
int PRE[100000],SCC[100000],PRE_CNT,SCC_CNT;
stack<int>STK;
int Dfs(const int u,const int parent)
{
    int low=PRE[u]=++PRE_CNT;
    STK.push(u);
    for(const int nxt:ET[u])if(nxt!=parent)
    {
        if(!PRE[nxt])getmin(low,Dfs(nxt,u));
        else if(SCC[nxt]==-1)getmin(low,PRE[nxt]);
    }
    if(low==PRE[u])
    {
        for(;;)
        {
            const int v=STK.top();STK.pop();
            SCC[v]=SCC_CNT;
            if(v==u)break;
        }
        SCC_CNT++;
    }
    return low;
}
int N;
void RebuildGraph()
{
    static vector<int>et_ans[100000];
    for(int i=0;i<N;i++)for(const int nxt:ET[i])
    {
        if(SCC[i]!=SCC[nxt])et_ans[SCC[i]].push_back(SCC[nxt]);
    }
    for(int i=0;i<SCC_CNT;i++)sort(et_ans[i].begin(),et_ans[i].end());
    for(int i=0;i<N;i++)ET[i].swap(et_ans[i]),vector<int>().swap(et_ans[i]);
}
void FindWinners(vector<int>&output)
{
    int *degree_in=new int[SCC_CNT],*scc_size=new int[SCC_CNT];
    for(int i=0;i<SCC_CNT;i++)degree_in[i]=scc_size[i]=0;
    for(int i=0;i<N;i++)scc_size[SCC[i]]++;
    for(int i=0;i<SCC_CNT;i++)for(const int nxt:ET[i])degree_in[nxt]++;
    queue<int>scc_win;
    set<int>unknown;
    for(int i=0;i<SCC_CNT;i++)
    {
        if(degree_in[i]==0)scc_win.push(i);
        else unknown.insert(i);
    }
    delete[]degree_in;
    output.clear();
    while(!scc_win.empty())
    {
        const int u=scc_win.front();scc_win.pop();
        output.push_back(u);
        for(auto nxt=unknown.begin();nxt!=unknown.end();)
        {
            const int edge_count=upper_bound(ET[u].begin(),ET[u].end(),*nxt)-lower_bound(ET[u].begin(),ET[u].end(),*nxt);
            if(edge_count<(long long)scc_size[u]*scc_size[*nxt])
            {
                scc_win.push(*nxt);
                unknown.erase(nxt++);
            }
            else nxt++;
        }
    }
    delete[]scc_size;
    bool *is_win=new bool[SCC_CNT];
    for(int i=0;i<SCC_CNT;i++)is_win[i]=false;
    for(const int v:output)is_win[v]=true;
    output.clear();
    for(int i=0;i<N;i++)if(is_win[SCC[i]])output.push_back(i);
    delete[]is_win;
}
int main()
{
//    freopen("in.txt","r",stdin);
    scanf("%d",&N);
    for(int i=0,k;i<N;i++)
    {
        ET[i].clear();
        scanf("%d",&k);
        for(int v;k--;)scanf("%d",&v),ET[i].push_back(--v);
    }
    for(int i=0;i<N;i++)PRE[i]=0,SCC[i]=-1;
    PRE_CNT=SCC_CNT=0;
    for(int i=0;i<N;i++)if(!PRE[i])Dfs(i,-1),assert(STK.empty());
    RebuildGraph();
    vector<int>ans;
    FindWinners(ans);
    printf("%d",(int)ans.size());
    for(const int v:ans)printf(" %d",v+1);
    puts("");
    return 0;
}