寒假第三天总结

晚上有点颓废的一天

上午洛谷春令营，起晚的锅就不提了…
大概讲了线段树及其变种&&扫描线技术&&二维数点&&主席树四部分内容，详细的专开一个blog。
下午开始狂写线段树，写了大概2h（期间连查带改），终于写出了我有生以来第一个线段树！！！
之后有纯写了大概1.7小时，AC了洛谷线段树模板的第二题。
最后也没睡午觉…
晚上助学课因为题没做所以只是随便听了下，之后有回放了下提高组的那个助学课。
听完课就去找主席树的资料了，然而找了一堆没有一个我期望中的板子…GG
然后心态爆炸看不进去…
后来计时打了一下tarjan，用时13min37s，其中多写了一个加入栈的操作，应该不会影响结果，后面比较dfn[j]与low[i]大小中ins[j]==1的条件忘记加了，这个可能会影响结果，其他的…没什么问题了吧…
最后贴上code充数：

//计时敲强连通分量tarjan算法
#include<bits/stdc++.h>
using namespace std;
const int maxn=10001,maxm=50001;
int m,n,belong[maxn],top=0,head[maxn],dfn[maxn],low[maxn],index=0,stap[maxn],stop=0,ins[maxn],f,g,bcnt=0;
struct node
{
    int to,next;
}edge[maxm];
inline void addedge(int x,int y)
{
    edge[++top].to=y;
    edge[top].next=head[x];
    head[x]=top;
    return;
}
inline void tarjan(int i)
{
    int j;
    dfn[i]=low[i]=++index;
    stap[++stop]=i;ins[i]=1;
    for(int k=head[i];k;k=edge[k].next)
    {
        int y=edge[k].to;
        if(!dfn[y])
        {
            tarjan(y);
            if(low[y]<low[i])low[i]=low[y];
        }
        else if(dfn[y]<low[i]&&ins[j])
        {
            low[i]=dfn[y];
        }
    }
    if(dfn[i]==low[i])
    {
        ++bcnt;
        do
        {
            j=stap[stop--];
            ins[j]=0;
            belong[j]=bcnt;
        }while(j!=i);
    }
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)dfn[i]=low[i]=ins[i]=0;
    while(m--)
    {
        scanf("%d%d",&f,&g);
        addedge(f,g);
    }
    for(int i=1;i<=n;i++)
    {
        if(!dfn[i])tarjan(i);
    }
    bcnt++;
    while(bcnt--)
    {
        for(int i=1;i<=n;i++)
            if(belong[i]==bcnt)
            {
                printf("%d ",i);
            }
        printf("\n");
    }
    return 0;
}