hdu 3394

题意：有一个公园有n个景点，公园的管理员准备修建m条道路，并且把参观路线安排成回路。如果一条道路被多条参观路线（也就是这个点连通分量含多个环）公用，那么这些参观路线中会有冲突；如果一条道路没在任何一个回路内（这个道路就是桥），那么这条路是不冲突的。问分别有多少条有没有冲突的路和有冲突的路（从例子里看含多个环的点双连通分量的全部边都是有冲突的）。
思路：
要形成环是求点的双连通分量，这样才满足只有一个环的双连通分量中的边数等于点数。
在点双连通分量中：
当点数=边数，形成一个环
当点数>边数（一条线段，说明这条边是桥）
当点数<边数，那么就含1个以上的环了
特殊情况，假设只有一条边a----b，a是顶点，不特判顶点会把a误认为是割点（a---b是割边倒没错，不会改变第一个答案），于是a-b就是点双连通分量，但是程序会算出这个双连通分量的边数和点数都是1，也就是一个桥，不会改变第二个答案，所以找割点时不特判是不是顶点不会影响结果。
桥的个数就是割边的数量，有冲突的路就是所有边数大于点数的点双连通分量的边数总和
用栈存储每个访问到的点，当找到割点也就是 $num[u]<=low[v]$ 时，已经访问完一个极大点双连通分量的访问，只需要将栈内的边一直出栈直到(u,v)出栈就停止。这些边都是这个极大点双连通分量的边。

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e4+5,maxm=2e5+5;
int head[maxn],Next[maxm],to[maxm],tot;
int ans1,ans2;//输出的结果 
int low[maxn],num[maxn],dfn;
bool vis[maxn];
void add(int x,int y) {
    to[++tot]=y;
    Next[tot]=head[x];
    head[x]=tot;
}
struct Node{
    int x,y;
}node;
stack<Node>st;
void tarjan(int u) {
    int x,y;
    int res=0,ans=0;
    memset(vis,false,sizeof vis);
    while(!st.empty()) {
        node=st.top();
        st.pop();
        x=node.x,y=node.y;
        ++ans;//该点连通分量中的边数 
        if(!vis[y]) {
            ++res;//该点连通分量中的点数
            vis[y]=true; 
        }
        if(x==u) break;
        if(!vis[x]) {
            ++res;
            vis[x]=true;
        }
    }
    if(ans>res) ans2+=ans;
}
void dfs(int u,int fa) {
    low[u]=num[u]=++dfn;
    for(int i=head[u];i;i=Next[i]) {
        int v=to[i];
        if(v==fa) continue;
        if(!num[v]) {
            st.push(Node{u,v});
            dfs(v,u);
            low[u]=min(low[u],low[v]);
            if(num[u]<=low[v]) {
                if(num[u]<low[v])
                    ++ans1;//割边的判定条件
                 tarjan(u); 
            }//判断割点和割边需要u！=1，但我们需要的是桥和含多个环的点连通分量 
        }//ans1一定是桥的数量，如果不是割点那么不会影响ans2的值 
        else if(num[v]<num[u]) {
            st.push(Node{u,v});
            low[u] = min(low[u], num[v]);
        }//有回退边
    }
}
int main() {
    int n,m;
    while(~scanf("%d%d",&n,&m)&&n) {
        memset(head,0,sizeof head);
        memset(num,0,sizeof num);
        for(int i=1;i<=m;++i) {
            int u,v;
            scanf("%d%d",&u,&v);
            ++u,++v;
            add(u,v),add(v,u);
        }
        tot=dfn=ans1=ans2=0;
        for(int i=1;i<=n;++i) if(!num[i])
            dfs(i,-1);
        printf("%d %d\n",ans1,ans2);
    }
    return 0;
}

hdu 3749

$多组输入，第一行输入N、M、Q，接着M行，每行两个数字(0\sim N-1)$ $表示两个点之间有一条边 ,然后Q次询问，问两个点之间$ $有多少个边不重复的路径，0个输出zero，1个输出one，两个或以上输出two$ $or$ $more$ 。
思路：两个点不在同一个连通块内就没有路径，点双连通分量中的任意两个点之间至少有两条路径（只有两个点的时候只有一条路径），不在同一个点双连通分量中两个点只有一条路径。并查集判断是否连通， $a[cnt][]$ 存第cnt个点双连通分量中的所有点， $b[u][]$ 存所有包含点u的点双连通分量， $b[u][i]==b[v][j]$ 判断 $u、v$ 是否在同一个点双连通分量内， $a[cnt].size()>2$ 判断点双连通分量是否不止两个点。
我在这题的讨论里还发了一些数据，就通过这些数据找到了自己的bug，我的代码中不能偷懒不设cnt给点双连通分量分“座位”直接用dfn来代替这个点双连通分量的编号（dfn是割点的编号），因为这个割点可能还是别的点双连通分量的割点，会出现将两个不同的点双连通分量合并的情况。
Code:

#include<bits/stdc++.h>
using namespace std;
const int maxn=5e3+50,maxm=2e4+50;
int head[maxn],Next[maxm],to[maxm],tot,all;
int fa[maxn];
int low[maxn],num[maxn],dfn;
int vis[maxn];
vector<int> a[maxn],b[maxn];
void add(int x,int y) {
    to[++tot]=y;
    Next[tot]=head[x];
    head[x]=tot;
}
struct Node{
    int x,y;
}node;
stack<Node>st;
int find(int x) {
    return fa[x]==-1?x:(fa[x]=find(fa[x]));
}
void tarjan(int u,int cnt) {
    int x,y;
    a[cnt].clear();
    while(!st.empty()) {
        node=st.top();
        st.pop();
        x=node.x,y=node.y;
        if(vis[y]!=cnt) {
            vis[y]=cnt;
            a[cnt].push_back(y);
            b[y].push_back(cnt);
        }
        if(x==u) break;
        if(vis[x]!=cnt) {
            vis[x]=cnt;
            a[cnt].push_back(x);
            b[x].push_back(cnt);
        }
    }
}
void dfs(int u,int fa) {
    low[u]=num[u]=++dfn;
    for(int i=head[u];i;i=Next[i]) {
        int v=to[i];
        if(v==fa) continue;
        if(!num[v]) {
            st.push(Node{u,v});
            dfs(v,u);
            low[u]=min(low[u],low[v]);
            if(num[u]<=low[v])
                tarjan(u,++all);
        }
        else if(num[v]<num[u]) {
            st.push(Node{u,v});
            low[u] = min(low[u], num[v]);
        }//有回退边
    }
}
int main() {
    int n,m,q,cas=0;
    while(~scanf("%d%d%d",&n,&m,&q)&&n) {
        memset(head,0,sizeof head);
        memset(vis,0,sizeof vis);
        memset(num,0,sizeof num);
        memset(fa,-1,sizeof fa);
        for(int i=0;i<=n;++i) b[i].clear();
        for(int i=1;i<=m;++i) {
            int u,v,x,y;
            scanf("%d%d",&u,&v);
            ++u,++v;
            add(u,v),add(v,u);
            x=find(u),y=find(v);
            if(x!=y) fa[y]=x;
        }
        tot=dfn=all=0;
        for(int i=1;i<=n;++i) if(!num[i])
            dfs(i,-1);
        printf("Case %d:\n",++cas);
        //for(int i=1;i<=all;++i) printf("%d ",a[i].size());
        //puts("");
        for(int i=1;i<=q;++i) {
            int u,v;
            scanf("%d%d",&u,&v);
            ++u,++v;
            if(find(u)!=find(v)) puts("zero");
            else {
                bool flag=true;
                for(auto i:b[u])
                for(auto j:b[v]) if(i==j) {
                    //printf("i==%d j==%d\n",i,j);
                    if(a[i].size()>2)    puts("two or more"),flag=false;
                }
                if(flag)    puts("one");
            }
        }
    }
    return 0;
}

hdu 2460

$多组输入，第一行输入N、M，接着M行，每行两个数字(1\sim N)$ $表示两个点之间有一条边 ,然后输入Q，接着输入Q组边表示在u和v之间$ $添加一条边，问每添加一条边图中桥的数量（前面添加的边在后$ $面依旧存在）$
思路：
1.求出原图中桥的数量，存入每个点的父亲(fa[v]=u)，于是可以通过标记v来表示u--v是否是割边。
2.每添加一条边后求出桥减少的数量
3.原来的-减少=答案
桥的数量就是割边的数量，桥就是两个边双连通分量之间的边。把一个边双连通分量中的所有点看成一个点（缩点），那么原图就成了一颗树，在两个点之间添加一条边就是在两个边双连通分量（可以是同一个边双连通分量）之间添加一条边。在u和v之间添加一条边，u到LCA(u，v)和v到LCA(u，v)路径上的所有边都会合成同一个边双连通分量，桥减少的数量就是路径上桥的数量。
Code：

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+7,maxm=4e5+7;
int head[maxn],Next[maxm],to[maxm],tot;
int low[maxn],num[maxn],dfn;
int fa[maxn],cnt,sum;
bool is_brige[maxn];
void add(int x,int y) {
    to[++tot]=y;
    Next[tot]=head[x];
    head[x]=tot;
}
void tarjan(int u,int f) {
    fa[u]=f;
    low[u]=num[u]=++dfn;
    for(int i=head[u];i;i=Next[i]) {
        int v=to[i];
        if(v==f) continue;
        if(!num[v]) {
            tarjan(v,u);
            low[u]=min(low[u],low[v]);
            if(num[u]<low[v])    ++cnt,is_brige[v]=true;
        }
        else if(low[u]>num[v])    low[u] = num[v];
    }
}
int main() {
    int n,m,q,cas=0;
    while(~scanf("%d%d",&n,&m)&&n) {
        memset(head,0,sizeof head);
        memset(is_brige,false,sizeof is_brige);
        memset(num,0,sizeof num);
        for(int i=1;i<=m;++i) {
            int u,v;
            scanf("%d%d",&u,&v);
            add(u,v),add(v,u);
        }
        tot=dfn=cnt=0;
        for(int i=1;i<=n;++i) tarjan(1,0);
        scanf("%d",&q);
        printf("Case %d:\n",++cas);
        for(int i=1;i<=q;++i) {
            int u,v;
            scanf("%d%d",&u,&v);
            while(u!=v) {
                if(is_brige[u]) {
                    is_brige[u]=false;
                    --cnt;
                }
                if(is_brige[v]) {
                    is_brige[v]=false;
                    --cnt;
                }
                u=fa[u],v=fa[v];
            }
            printf("%d\n",cnt);
        }
        puts("");
    }
    return 0;
}

hdu 4587

$多组输入，第一行输入N、M，接着M行，每行两个数字(0\sim N-1)$ $表示两个点之间有一条边 ,问任意删除两点，最多有多少个连通块。$
思路：首先想到删掉割点会将一个连通块分成多个连通块，如果都删割点不一定是最优的（如图，删除a、b只只会产生一个连通分量，如果删掉一个d在删掉b就是最优的了）。
图片说明
枚举第一个删掉的点，第二个删掉割点，得到的结果一定是最优的。
枚举第一个删掉的点后跑一遍图， $num[i]==0$ 就以点 $i$ 为根结点跑这个连通分量，同时 $--iscut[i],++left$ ，left表示删掉第一个结点后连通分量的总数，跑图时用 $iscut[]$ 标记割点孩子的数量，删除的第二个结点应该是 $i，{iscut[i]}_{max}\&\&i!=x$ 。每次枚举完的结果就是 $iscut[i]_{max}+1+left-1$ 。+1是删掉割点，祖先也会独立成一个连通分量，根结点没有父亲（默认它是割点，其实如果它只有一个孩子就不是，这里不作区别），所以要 $--iscut[i]$ 预处理一下，-1是因为第二个删掉割点产生 $iscut[i]+1$ 个连通分量的前提是left里的一个连通分量被分解。
注意：当只有两个点时或者删掉的第一个结点的孩子都是叶子结点时， $iscut[i]_{max}==-1$ ,如果 $iscut[x]_{max}==0$ （x是第一个删掉的点）就会影响结果。
Code：

#include<bits/stdc++.h>
using namespace std;
const int maxn=5e3+7,maxm=1e4+7;
int head[maxn],Next[maxm],to[maxm],tot;
int num[maxn],dfn;
int iscut[maxn],none,res,now_left,ans,n,m;
void add(int x,int y) {
    to[++tot]=y;
    Next[tot]=head[x];
    head[x]=tot;
}
int tarjan(int u,int fa) {
    int lowu=num[u]=++dfn;
    for(int i=head[u];i;i=Next[i]) {
        int v=to[i];
        if(v==fa||v==none) continue;
        if(!num[v]) {
            int lowv=tarjan(v,u);
            lowu=min(lowu,lowv);
            if(num[u]<=lowv)    ++iscut[u];
        }
        else if(lowu>num[v])    lowu = num[v];
    }
    return lowu;
}
int solve(int x) {
    memset(iscut,0,sizeof iscut);
    memset(num,0,sizeof num);
    none=x,iscut[x]=-1,dfn=now_left=res=0;
    for(int i=1;i<=n;++i) if(i!=x&&!num[i]) 
        --iscut[i],++now_left,tarjan(i, -1);
    for(int i=1;i<=n;++i) res=max(res,iscut[i]+1);
    return res+now_left-1;
}
int main() {
    while(~scanf("%d%d",&n,&m)) {
        memset(head,0,sizeof head);
        ans=tot=0;
        for(int i=1;i<=m;++i) {
            int u,v;
            scanf("%d%d",&u,&v);
            ++u,++v;
            add(u,v),add(v,u);
        }
        for(int i=1;i<=n;++i)
            ans=max(ans,solve(i));
        printf("%d\n",ans);
    }
    return 0;
}

点、边双连通图练习

hdu 3394

hdu 3749

hdu 2460

hdu 4587