[图论]割边的算法

啊哈磊

[code=Cpp width=740px]#include <stdio.h>
#define MAX 9
int n,m,e[MAX][MAX],root;
int dfn[MAX],low[MAX],flag[MAX],index;
int min(int a,int b)
{
    return a < b ? a : b;
}
void dfs(int cur,int father)
{
    int i,j;

    index++;
    dfn[cur]=index;
    low[cur]=index;
    for(i=1;i <= n;i++)
    {
        if(e[cur]==1)
        {
            if(dfn==0)
            {
                dfs(i,cur);
                low[cur]=min(low,low[cur]);
                if(low > dfn[cur])
                    printf("%d-%d\n",cur,i);
            }
            else if(i != father)
            {
                low[cur]=min(low[cur],dfn);
            }
        }
    }  
}
int main()
{
        freopen("edge.in","r",stdin);
    freopen("edge.out","w",stdout);
    int i,j,x,y;
    scanf("%d %d",&n,&m);
    for(i=1;i <= n;i++)
        for(j=1;j <= n;j++)
            e[j]=0;

    for(i=1;i <= m;i++)
    {
        scanf("%d %d",&x,&y);
        e[x][y]=1;
        e[y][x]=1;
    }
    root=1;
    dfs(1,root);  

    for(i=1;i <= n;i++)
    {
        if(flag==1)
            printf("%d ",i);
    }
    return 0;
}[/code]