[PA 2006 Round4][SCC] Crayfish

原題連結
這道題一開始我想的蠻歪的
我第一個solution是使用dp[maxn][2]代表該狀態下能夠到達的所有點個數，然後去dfs之後算出該次ans，再將該次有到達的所有狀態的答案設為ans。

不過這樣做的錯誤其實蠻顯然的。首先是A走到B但B顯然不一定能走回A，那麼這樣算出的答案必定錯誤，再來是題目要求從某點出發需是倒退狀態，還需要能夠從倒退狀態下回來，而這樣dfs並沒有考慮到能否回來。

那要怎麼修改錯誤呢？先注意到第二個錯誤，如果我們想從某點出發還能夠回來某點，這不就是強連通的概念嗎？而且如果能夠套用強連通的概念，那麼在同一個強連通分量裡的答案確實應該是一樣的！（想一想，為什麼）想到了強連通分量後，我們同時修正了兩個錯誤！

剩下的問題就是，這題的狀態除了「在哪個點」之外還有「前進or倒退」共兩個因素，這時候就要靠點經驗和直覺了。將每個點拆成兩個點，一個代表前進狀態，另一個代表後退狀態，那麼只要想清楚如何建邊，再套用SCC算法(Kosaraju or Tarjan)，最後計算出的每個SCC的size然後輸出答案就好。

整體來說，我覺得這題對於像我這樣的新手(弱）來說相當不錯。沒有太複雜的流程和太過精妙的巧思，但也不是不用思考的模板題。

#include<cstdio>
#include<cstdlib>
#include<vector>
#include<stack>
using namespace std;
const int maxn=20000+5;
vector<int> G[maxn];
int n,m,sccno[maxn],pre[maxn],dfs_clock,scc_cnt;
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=S.top();S.pop();
            sccno[x]=scc_cnt;
            if(x==now) break;
        }
    }
    return lownow;
}
int size[maxn],ans[maxn],vis[maxn];
void find_scc()
{
    dfs_clock=scc_cnt=0;
    for(int i=0;i<n*2;i++) if(!pre[i]) dfs(i);
    for(int i=0;i<n*2;i++) if(vis[i/2]!=sccno[i]) size[sccno[i]]++,vis[i/2]=sccno[i];
    for(int i=1;i<n*2;i+=2) printf("%d\n",size[sccno[i]]-1);
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=0,a,b,c;i<m;i++) // i*2:normal,i*2+1:back
    {
        scanf("%d%d%d",&a,&b,&c);a--,b--;
        if(c) // change status
        {
            G[a*2].push_back(b*2+1);
            G[b*2+1].push_back(a*2);
        }
        else // still
        {
            G[a*2].push_back(b*2);
            G[b*2+1].push_back(a*2+1);
        }
    }
    find_scc();
}