BZOJ1718: [Usaco2006 Jan] Redundant Paths 分离的路径【边双连通分量】

1718: [Usaco2006 Jan] Redundant Paths 分离的路径

【题目描述】

传送门

【题解】

(边双连通分量叶节点数量+1)/2。

代码如下

#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
const int MAXN=5005,MAXE=10005;
int n,m,Top,Ans,tim,cnt,Fa[MAXN],Stk[MAXN],Dfn[MAXN],Low[MAXN],C[MAXN];
bool vis[MAXN];
struct Edge{
    int tot,lnk[MAXN],son[MAXE<<1],nxt[MAXE<<1];
    void clear(){memset(lnk,-1,sizeof(lnk));tot=-1;}
    void Add(int x,int y){son[++tot]=y;nxt[tot]=lnk[x];lnk[x]=tot;}
}E;
void Tarjan(int x,int fa){
    Dfn[x]=Low[x]=++tim;vis[Stk[++Top]=x]=1;
    for(int j=E.lnk[x];j^-1;j=E.nxt[j])
    if(j!=fa){
        if(!Dfn[E.son[j]]) Tarjan(E.son[j],j^1),Low[x]=min(Low[x],Low[E.son[j]]);
        else if(vis[E.son[j]]) Low[x]=min(Low[x],Dfn[E.son[j]]);
    }
    if(Dfn[x]==Low[x]){++cnt;do{Fa[Stk[Top]]=cnt,vis[Stk[Top]]=0;}while(Stk[Top--]!=x);}
}
int main(){
    #ifndef ONLINE_JUDGE
    freopen("prob.in","r",stdin);
    freopen("prob.out","w",stdout);
    #endif
    scanf("%d%d",&n,&m);E.clear();
    for(int i=1,x,y;i<=m;i++) scanf("%d%d",&x,&y),E.Add(x,y),E.Add(y,x);
    for(int i=1;i<=n;i++) if(!Dfn[i]) Tarjan(i,-1);
    for(int i=1;i<=n;i++)
    for(int j=E.lnk[i];j^-1;j=E.nxt[j])
    if(Fa[i]!=Fa[E.son[j]]) C[Fa[i]]++;
    for(int i=1;i<=cnt;i++) Ans+=(C[i]==1);
    printf("%d\n",(Ans+1)/2);
    return 0;
} 

发表评论

电子邮件地址不会被公开。 必填项已用*标注

开始在上面输入您的搜索词,然后按回车进行搜索。按ESC取消。

返回顶部