[POI XI Stage II][SCC] The Tournament

原題連結

我個人非常喜歡這道題，主要是因為直到我AC前的2個小時，我都完全沒想到這題是SCC的一道題XD。
最後雖然發現了和SCC的強大關聯性，還是借用了同學的code，而且想了非常久才弄出來的......

定理1：對於在同一強連通分量裡的所有點，他們要不全都可以當冠軍，要不全都不行。
定理2：對於任何一個已確定可以當上冠軍的強連通分量A，則對於任意非A的強連通分量B若存在點s在A中且點t在B中，且s到t沒有邊，則B也可以當上冠軍。
定理2也可以描述成這樣：
一強連通分量A不是冠軍分量(?)若且唯若所有冠軍分量都完全壓制A(即不滿足定理2)。

證明並不困難，直接考慮構造方案就可以了。

有這兩個定理就很好做了......還是不懂的童鞋可以直接參考code

#define LL long long
#include<queue>
#include<algorithm>
#include<stack>
#include<cstdio>
#include<cstdlib>
#include<vector>
#include<set>
using namespace std;
const int maxn=100000+5;
vector<int> G[maxn];
int n,sccno[maxn],scc_cnt,dfs_clock,pre[maxn];
stack<int> S;
int dfs(int now)
{
    S.push(now);
    int lownow=pre[now]=++dfs_clock;
    for(int i=0;i<G[now].size();i++)
    {
        int to=G[now][i];
        if(!pre[to])
        {
            int lowto=dfs(to);
            lownow=min(lownow,lowto);
        }
        else if(!sccno[to]) lownow=min(lownow,pre[to]);
    }
    if(lownow==pre[now])
    {
        scc_cnt++;
        for(int x=-1;x!=now;)
        {
            x=S.top();S.pop();
            sccno[x]=scc_cnt;
        }
    }
    return lownow;
}
int ans[maxn],scc_ind[maxn];
LL scc_size[maxn];
vector<int> sccG[maxn];
set<int> Set;
void find_scc()
{
    scc_cnt=dfs_clock=0;
    for(int i=0;i<n;i++) if(!pre[i]) dfs(i);
    for(int now=0;now<n;now++)
    {
        scc_size[sccno[now]]++;
        for(int i=0;i<G[now].size();i++)
        {
            int to=G[now][i];
            if(sccno[to]==sccno[now]) continue;
            sccG[sccno[now]].push_back(sccno[to]);
            scc_ind[sccno[to]]++;
        }
    }
    queue<int> Q;
    for(int i=1;i<=scc_cnt;i++)
    {
        if(!scc_ind[i]) ans[i]=1,Q.push(i);
        else Set.insert(i);
    }
    while(!Q.empty())
    {
        int now=Q.front();Q.pop();
        sort(sccG[now].begin(),sccG[now].end());
        vector<int> still;
        for(int L=0;L<sccG[now].size();)
        {
            int to=sccG[now][L],R=L;
            while(R<sccG[now].size() && sccG[now][R]==to) R++;
            if((LL)(R-L)==scc_size[now]*scc_size[to] && Set.find(to)!=Set.end())
            {
                still.push_back(to);
                Set.erase(to);
            }
            L=R;
        }
        for(set<int>::iterator it=Set.begin();it!=Set.end();it++)ans[*it]=1,Q.push(*it);
        Set.clear();
        for(int i=0;i<still.size();i++) Set.insert(still[i]);
    }
    int cnt=0;
    for(int i=0;i<n;i++) if(ans[sccno[i]]) cnt++;
    printf("%d",cnt);
    for(int i=0;i<n;i++) if(ans[sccno[i]]) printf(" %d",i+1);puts("");
}
main()
{
    scanf("%d",&n);
    for(int i=0,k,x;i<n;i++)
    {
        scanf("%d",&k);
        while(k--) {scanf("%d",&x);x--;G[i].push_back(x);}
    }
    find_scc();
}