首页 > 代码库 > zoj2588 Burning Bridges --- 求割边
zoj2588 Burning Bridges --- 求割边
#include <iostream> #include <cstring> #include <string> #include <cstdio> #include <cmath> #include <algorithm> #include <vector> #include <queue> #include <map> #define inf 0x3f3f3f3f #define eps 1e-6 #define ll __int64 using namespace std; #define N 10010 #define M 100010 struct node//边结点 { int v,tag,id;//v为所连接的另一个结点,tag为重边数,id为序号 node *next; }; int n,m;//点,边数 int nid;//输入时边的序号 node mem[M*2];int memp;//mem为存储边结点的数组,memp为mem数组序号 node *e[N];//邻接表 int brig[M];//brig[i]=1表示第i+1条边为割边 int nbrig;//求得割边的数目 int low[N],dfn[N];//low[i]为顶点i可达祖先的最小编号,dfn[i]为深度优先数 int vis[N];//0未访问 1已访问 2已访问且已检查邻接结点 //在邻接表中插入边(i,j),若有重边,则只把相应边结点的tag+1 int addedge(int i,int j) { node* p; for(p=e[i];p!=NULL;p=p->next) if(p->v==j) break; if(p!=NULL) { p->tag++; return 0; } p=&mem[memp++]; p->v=j; p->next=e[i]; e[i]=p; p->id=nid; p->tag=0; return 1; } //参数含义:i为当前搜索的顶点,father为i的父节点,dth为搜索深度 void dfs(int i,int father,int dth) { vis[i]=1; dfn[i]=low[i]=dth; node* p; for(p=e[i];p!=NULL;p=p->next) { int j=p->v; if(j!=father&&vis[j]) low[i]=min(low[i],dfn[j]); if(!vis[j]) { dfs(j,i,dth+1); low[i]=min(low[i],low[j]); if(low[j]>dfn[i]&&!p->tag) brig[p->id]=++nbrig; } } vis[i]=2; } void init() { memp=nid=nbrig=0; memset(e,0,sizeof e); memset(brig,0,sizeof brig); memset(vis,0,sizeof vis); } int main() { int t,i,j,a,b; scanf("%d",&t); while(t--) { scanf("%d%d",&n,&m); init(); for(i=0;i<m;i++) { scanf("%d%d",&a,&b); addedge(a-1,b-1); addedge(b-1,a-1); nid++; } dfs(0,-1,1); printf("%d\n",nbrig); for(i=0,j=nbrig;i<m;i++) { // printf("i:%d brig[i]:%d\n",i+1,brig[i]); if(brig[i]) { printf("%d",i+1); if(--j) putchar(' '); } } if(nbrig) puts(""); if(t) puts(""); } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。