省赛倒计时13天

众所周知:Tarjan算法是解决强连通分量和缩点的常见方法。

P2835 刻录光盘

分析各个数组的作用: dfn:该点第几次被遍历到 low:该点及其子树最早被遍历到的次序号。 inq:改点是否在栈中 bl:改点属于第几个强连通分量 sz:该强连通分量中包含几个点 in:强连通分量中的入读关系，若为0则说明该分量并没有被其他分量指向。

#include 
using namespace std;
const int N=6e5+5;
int head[N],nxt[N],v[N],n,cnt,ans;
int dfn[N],low[N],inq[N],ti,tol,bl[N],sz[N],in[N];
stackq;
void add(int from,int to)
{
    v[++cnt]=to;
    nxt[cnt]=head[from];
    head[from]=cnt;
}
void tarjan(int u)
{
    dfn[u]=low[u]=++ti;
    q.push(u);
    inq[u]=1;
    for(int i=head[u];i;i=nxt[i])
    {
        int j=v[i];
        if(!dfn[j])
        {
            tarjan(j);
            low[u]=min(low[u],low[j]);
        }
        else if(inq[j])
            low[u]=min(low[u],dfn[j]);
    }
    if(dfn[u]==low[u])
    {
        tol++;int tmp;
        do
        {
            tmp=q.top();q.pop();
            inq[tmp]=0;
            bl[tmp]=tol;sz[tol]++;
        }while(tmp!=u);
    }
}
int main()
{
    cin>>n;
    for(int i=1;i>x&&x)
            add(i,x);
    }
    for(int i=1;iw||!check(a[g].first,ss))
            cout