原题链接

    无向连通图中,如果删除某边后,图变成不连通,则称该边为桥。

  也可以先用Tajan()进行dfs算出所有点 的low和dfn值,并记录dfs过程中每个 点的父节点;然后再把所有点遍历一遍, 看其low和dfn,满足dfn[ fa ]<low[ i ](0<i<=n, i 的 father为fa) —— 则桥为fa-i。 找桥的时候,要注意看有没有重边;有重边,则不是桥。

  另外,本题的题意及测试样例中没有重边,所以不用考虑重边。

  


带详细注释的题解:

#include<stdio.h>
#include<string.h>
#include<math.h>
#include<iostream>
#include<algorithm>
#include<stack>
#include<vector>
#define maxn 10010
using namespace std;
int dfn[maxn],low_link[maxn] ,Father[maxn];
//tarjan 算法的dfn ——在DFS过程中 的访问序号(也可以叫做开始时间
//tarjan 算法的low_link[i]——从i节点出发DFS过程中i下方节点所能到达的最早的节点的 开始时间
int bridgenum, Time ,n ; //桥的总数,dfn时间戳,n为顶点数,
vector<int>G[maxn]; //定义图的邻接矩阵表
stack<int>st;
struct node{
int u,v;
}bridge[maxn]; //整个图的桥的存储
bool cmp( node a,node b )
{
if(a.u!=b.u)return a.u<b.u;
else return a.v<b.v;
}
void init(){
int i;
for(i=;i<=n;i++) //初始化邻接表
G[i].clear();
bridgenum=;Time=;
memset(dfn,,sizeof(dfn));
memset(low_link,,sizeof(low_link));
memset(Father,,sizeof(Father));
}
void tarjan(int u,int fa)
{
low_link[u]=dfn[u]=++Time;
Father[u]=fa; //记录父节点
// st.push(u);
for(int i=;i<(int)G[u].size();i++){
int v=G[u][i];
if(!dfn[v]){
tarjan(v,u);
low_link[u]=min(low_link[u],low_link[v]);
}
else if(v!=fa){ //不能连接到父节点!
low_link[u]=min(low_link[u],dfn[v]);
}
else{
//这种情况就是有重边的情况!不予处理,直接跳过!
}
}
}
void solve()
{
for(int i=;i<n;i++){
if(!dfn[i])
tarjan(i,-);
}
int ans=;
for(int i=;i<n;i++){
int v=Father[i];
if(dfn[v]<low_link[i]&&v!=-){ //若v-i可以构成父节点
bridge[ans].u=v; //桥的两条边
bridge[ans].v=i;
if(bridge[ans].u>bridge[ans].v)
swap(bridge[ans].u,bridge[ans].v);
ans++;
}
}
sort(bridge,bridge+ans,cmp);
printf("%d critical links\n",ans);
for(int i=;i<ans;i++){
printf("%d - %d\n",bridge[i].u,bridge[i].v);
}
}
int cal_num(char ch[]){
int len=strlen(ch),s=;
for(int i=;i<=len-;i++){
s=s*+ch[i]-'';
}
return s;
}
int main()
{
int T,cas=;
scanf("%d",&T);
while(T--)
{
init();
char ch[];
int m ,u,v; //边数
scanf("%d",&n);
for(int i=;i<=n;i++){
scanf("%d%s",&u,ch);
m=cal_num(ch); //截取出数字存入m——边数
for(int j=;j<=m;j++){
scanf("%d",&v);
G[u].push_back(v); //这里按单向边任意一边存储就可以了,毕竟是无向图!
G[v].push_back(u);
}
}
printf("Case %d:\n",++cas);
solve();
}
return ;
}

最新文章

  1. 别不信!App三年内将被HTML5顶替彻底消失?
  2. SCOI2005栅栏
  3. ASP.NET MVC ValueProvider小结
  4. php 以图搜图
  5. CentOS7 增加tomcat 启动,停止,使用systemctl进行配置
  6. 【Android】Android内存机制,了解Android堆和栈
  7. sql表设计器的几个默认值
  8. iOS 推送证书
  9. Python递归遍历目录下所有文件
  10. Delphi实用小function
  11. 排序算法(冒泡,选择,快速)Java 实现
  12. opencv视频跟踪2
  13. gauge.js的应用
  14. swift3.0 扩展、协议(4)
  15. .NET技术基础总结 ----第一章
  16. rabbitmq的构架和原理(三)
  17. 卷积神经网络(CNN)中卷积的实现
  18. mysql远程连接很慢问题解决
  19. API网关学习及介绍
  20. program与module

热门文章

  1. 【转载】我为什么放弃了 Linux 内核学习?
  2. spring结合shiro的学习总结
  3. 《构建之法》——GitHub和Visual Studio的基础使用
  4. Java网络编程探究|乐字节
  5. 016 Android 图片选择器(在选中和未选中的过程中,切换展示图片)
  6. 17 SUMIF函数、countif函数、averagif函数
  7. WUSTOJ 1335: Similar Word(Java)
  8. closed channel
  9. hadoop 空间配置
  10. Kettle部署笔记