所以图论的题给的难度都这么高吗= =

一道割点的模板题,我这里是用的tarjan算法的思想,但是这题和tarjan不完全相同。

其实当时自己写的时候犯了一个低级错误,所以感觉习惯好还是很重要。

···cpp

#include<cstdio>
struct node{
    int from,to;
    int next;
}e[200010];//邻接表用来存储图 
int root,len,n,m,sum,ans;
int head[100010],dfn[100010],low[100010],vis[100010],poi[100010];
int rin(){//最常规的读入优化 
    char ch=getchar();
    int sum=0;
    while (ch<'0'||ch>'9') ch=getchar();
    while (ch>='0'&&ch<='9'){
        sum=sum*10+ch-'0';
        ch=getchar();
    }
    return sum;
}
int fmin(int a,int b){return a<b?a:b;}//用这个是因为个人习惯,代替min函数使用 
void add(int x,int y){//邻接表增加无向边 
    e[++len].to=y;
    e[len].from=x;
    e[len].next=head[x];
    head[x]=len;
    e[++len].to=x;
    e[len].from=y;
    e[len].next=head[y];
    head[y]=len;
}
void tarjan(int u,int fa){//其实这题使用的并不是原版的tarjan而是做了一些改动 
    int son=0;
    vis[u]=1; dfn[u]=low[u]=++sum;//这个点现在查找过 
    for(int i=head[u];i!=0;i=e[i].next){//查找该点可以到达的点 
        int v=e[i].to; 
        if(vis[v]==1&&v!=fa) low[u]=fmin(low[u],dfn[v]);//如果这个点已经到过并且v不是u的父节点就不是割点,只需要做low更新处理 
        else if(dfn[v]==0){//如果该点未到达就搜索,u作为v的父节点传递 
            tarjan(v,u); 
            son++;//u的孩子数增加 
            low[u]=fmin(low[u],low[v]);//更新low 
            if((fa==-1&&son>1)||(fa!=-1&&dfn[u]<=low[v])){//如果该点是根节点并且孩子数大于1,或者该点并不是根节点但是dfn[u]<=low[v],这个点就是根节点
                if (poi[u]==0) ans++;//ans记录割点的数量 
                poi[u]=1;//将u标记成割点 
            }
        }
    }
    vis[u]=2;//这里其实可加可不加,但是这样做循环次数会变少。 
}
void inpt(){//输入处理 
    n=rin(); m=rin();
    for (int i=1;i<=m;i++){
        int x,y;
        x=rin(); y=rin();
        add(x,y);//加无向边 
    }
}
void work(){//工作处理 
    for (int i=1;i<=n;i++)
        if (!dfn[i])//因为这个题是不一定只有一个联通分量所以这样判断 
            tarjan(i,-1);
}
void outp(){//输出处理 
    printf("%d\n",ans);//输出ans 
    for (int i=1;i<=n;i++)
        if (poi[i]) printf("%d ",i);//如果该点是割点就输出 
    printf("\n");
}
int main(){
    inpt();
    work();
    outp();
    return 0;
}

··· --我当时错误的地方是我自己写的fmin出错了,我求最小值结果求的是最大值,23333--