题目链接:http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=1588

题意:Ferry王国有n个岛,m座桥,每个岛都可以互达,现在要烧毁一些桥使得,但烧毁后每个岛仍可以互达,问哪些桥肯定不会被烧毁。

分析:给定一个无向连通图,要求图中的割边。注意,图中可能有重边,只要顶点u和v之间有重边,则这些重边任何一条都不可能是割边。这题的输出比较坑,pe了好多次。。。

AC代码:

 #include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=+;
const int M=+;
struct EDGE{
int v,id,next;
}edge[M*];
int first[N],low[N],dfn[N],bri[M];
int g,cnt,top,ans;
int min(int a,int b)
{
return a<b?a:b;
}
void AddEdge(int u,int v,int id)
{
edge[g].v=v;
edge[g].id=id;
edge[g].next=first[u];
first[u]=g++;
}
void Tarjan(int u,int fa)
{
int i,v;
low[u]=dfn[u]=++cnt;
for(i=first[u];i!=-;i=edge[i].next)
{
v=edge[i].v;
if(i==(fa^))
continue;
if(!dfn[v])
{
Tarjan(v,i);
low[u]=min(low[u],low[v]);
if(low[v]>dfn[u])
{
bri[top++]=edge[i].id;
ans++;
}
}
else
low[u]=min(low[u],dfn[v]);
}
}
int main()
{
int t,n,m,i,u,v;
scanf("%d",&t);
while(t--)
{
g=cnt=top=ans=;
memset(first,-,sizeof(first));
memset(low,,sizeof(low));
memset(dfn,,sizeof(dfn));
memset(bri,M,sizeof(bri));
scanf("%d%d",&n,&m);
for(i=;i<=m;i++)
{
scanf("%d%d",&u,&v);
AddEdge(u,v,i);
AddEdge(v,u,i);
}
for(i=;i<=n;i++)
if(!dfn[i])
Tarjan(i,-);
sort(bri,bri+top);
printf("%d\n",ans);
for(i=;i<top;i++)
{
printf("%d",bri[i]);
if(i!=top-)
printf(" ");
}
if(top)
printf("\n");
if(t)
printf("\n");
}
return ;
}

最新文章

  1. Spring2.0-applicationContext.xml中使用el表达式给实体类属性赋值被当成字符串-遁地龙卷风
  2. 【代码笔记】iOS-图片手势,上传照片
  3. vCSA加域&amp;vcenter关联域&amp;设置管理员权限
  4. PHP多条件搜索ShopNc实例
  5. 优雅的使用python之环境管理
  6. C语言学习016:单链表
  7. springmvc 项目完整示例06 日志–log4j 参数详细解析 log4j如何配置
  8. Java笔记——JavaMail发送邮件
  9. iOS开发-解决AVAudioRecorder录音文件无法保存的问题
  10. Red hat Linux(Centos 5/6)安装R语言
  11. MyEclipse 多项目对应配置多个Tomcat
  12. OOP 概述
  13. asp.net连接ORACLE数据库
  14. Nodejs --我自己的学习笔记
  15. 基于vue的多引擎搜索及关键字提示
  16. 基于FPGA的IIR滤波器
  17. CodeForces776-A.Serial Killer-string
  18. CentOS配置samba服务
  19. Fliptile [POJ3279] [开关问题]
  20. sprintf() 处理 float类型的数字,保留小数位等。

热门文章

  1. Gitlab+Jenkins学习之路(十三)之发布Java项目到tomcat
  2. Java Swing:JPanel中添加JPanel
  3. JAVAWEB 遍历mysql结果集时 字段为0、false、null的问题
  4. SSISDB2:SSIS工程的操作实例
  5. 关于dbw 与dbm 的计算
  6. Jmeter接口测试(五)变量及参数化
  7. Docker--Dockerfile引用及指令集的功能用法
  8. 【python 2.7】输入任意字母数字,输出其对应的莫尔斯码并播放声音
  9. 企业上云这四大要点,你 get 了吗?
  10. pkill命令详解