3/24 阅读博客三篇+今日《并查集》

今日阅读博客: 一道题弄懂递归、深度优先搜索、记忆化搜索、DP动态规划 关于tarjan算法的一些理解（割点割边） 卡特兰数（好像很有用的说） 卡特兰数：C(n)=C(n-1)((4n-2)/(n+1)) C2n （n）=(2n!)/(n!)²

二分图着色技巧：

void color(int u,int pre,int c)
{
    col[u]=c;
    for(int i=head[u];i;i=e[i].nxt)
    {
        int v=e[i].to;
        if(!col[v])
        dfs(v,u,3-color); //分成两类
    }
    return；
}

求割点：割点满足条件： 1.改点子树数量>=2 2.对于边(u, v)，如果low[v]>=dfn[u]，此时u就是割点

void tarjan(int u,int mr)
{
    dfn[u]=low[u]=++tim;
    q.push(u);
    inq[u]=1;
    int rc=0;
    for(int i=head[u];i;i=nxt[i])
    {
        int v1=v[i];
        if(!dfn[v1])
        {
            tarjan(v1,mr);
            low[u]=min(low[u],low[v1]);
            if(low[v1]>=dfn[u]&&u!=mr)
                vis[u]=1;
            if(u==mr)
                rc++;
        }
        else if(inq[v1])
            low[u]=min(low[u],dfn[v1]);
    }
    if(dfn[u]==low[u])
    {
        tol++;int tmp;
        do{
            tmp=q.top();
            q.pop();
            inq[tmp]=0;
        }while(tmp!=u);
    }
    if(u==mr&&rc>=2)
        vis[u]=1;
}

求割边：对于一条边如果它是割边的话，那么low[v] > dfn[u] ,也就是以v为根的子树是封闭的，只要去掉u,v连接的这条边，就会增加联通分量的数量

		if(!dfn[v1])
        {
            tarjan(v1,mr);
            low[u]=min(low[u],low[v1]);
            if(low[v1]>dfn[u]&&u!=mr)
                vis[u]=1;
        }
        else if(inq[v1])
            low[u]=min(low[u],dfn[v1]);

求一个数的二进制表示（用补码表示）

void complement(int i,int step)//倒序输出后7位
{
	if (step ==9)return;
	f(i >> 1, step + 1);
	if (i & 1)cout t;
    for(int i=1;i>c>>i>>j;
        fx=r_find(i),fy=r_find(j);
        if(c=='M')
        {

            f[fx]=fy;
            dis[fx]+=sz[fy]; //更新x的根到y的根距离
            sz[fx]+=sz[fy];  //更新集合大小
            sz[fy]=sz[fx];   //更新
        }
        else if(c=='C')
        {
            if(fx!=fy)
            {
                cout