传送门:Critical Links

题意:给出一个无向图,按顺序输出桥。

分析:模板题,求出桥后排个序输出。

#include <cstdio>
#include <cstring>
#include <string>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <queue>
#include <cstdlib>
#include <stack>
#include <vector>
#include <set>
#include <map>
#define LL long long
#define mod 100000000
#define inf 0x3f3f3f3f
#define eps 1e-6
#define N 10010
#define FILL(a,b) (memset(a,b,sizeof(a)))
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define PII pair<int,int>
using namespace std;
struct edge
{
int v,next;
edge(){}
edge(int v,int next):v(v),next(next){}
}e[N<<];
struct bridge
{
int u,v;
bridge(){}
bridge(int u,int v):u(u),v(v){}
bool operator<(const bridge &a)const{
if(u==a.u)return v<a.v;
return u<a.u;
}
}b[N<<];
int n,step,top,tot,num;
int head[N],dfn[N],low[N],Stack[N];
bool instack[N],vis[N<<];
map<int,int>mp;
void init()
{
tot=;step=;top=;num=;
FILL(head,-);FILL(dfn,);
FILL(low,);FILL(instack,false);
FILL(vis,);mp.clear();
}
bool isHash(int u,int v)
{
if(mp[u*N+v])return ;
if(mp[v*N+u])return ;
mp[u*N+v]=mp[v*N+u]=;
return ;
}
void addedge(int u,int v)
{
e[tot]=edge(v,head[u]);
head[u]=tot++;
}
void tarjan(int u)
{
dfn[u]=low[u]=++step;
Stack[top++]=u;
instack[u]=true;
for(int i=head[u];~i;i=e[i].next)
{
int v=e[i].v;
if(vis[i])continue;
vis[i]=vis[i^]=;
if(!dfn[v])
{
tarjan(v);
if(low[u]>low[v])low[u]=low[v];
//桥:一条无向边(u,v)是桥,当且仅当(u,v)为树枝边,且满足DFS[u]<Low[v]
if(low[v]>dfn[u])
{
b[num++]=bridge(min(u,v),max(u,v));
}
}
else if(low[u]>dfn[v])
{
low[u]=dfn[v];
}
}
instack[u]=false;
top--;
}
void solve()
{
for(int i=;i<n;i++)
if(!dfn[i])tarjan(i);
sort(b,b+num);
printf("%d critical links\n",num);
for(int i=;i<num;i++)
printf("%d - %d\n",b[i].u,b[i].v);
puts("");
}
int main()
{
int u,v;
while(scanf("%d",&n)>)
{
init();
for(int i=;i<=n;i++)
{
int t,u,v;
scanf("%d (%d)",&u,&t);
while(t--)
{
scanf("%d",&v);
if(!isHash(u,v))
{
addedge(u,v);
addedge(v,u);
} }
}
solve();
}
}

最新文章

  1. elasticsearch常用的概念整理
  2. codeigniter钩子的使用
  3. go:windows下用sublime Text搭建go语言开发环境
  4. Runtime获取一个类中所有成员变量的名字和类型
  5. SQL server 测试
  6. 转:[ASP.NET]重構之路系列v4 – 簡單使用interface之『你也會IoC』
  7. 《C语言入门1.2.3—一个老鸟的C语言学习心得》—清华大学出版社炮制的又一本劣书及伪书
  8. This implementation is not part of the Windows Platform FIPS validated cryptographic algorithms
  9. Perl的主要应用领域
  10. Java API —— 网络编程
  11. HDU5727 Necklace
  12. yaffs2文件系统
  13. Divide and Conquer.(Merge Sort) by sixleaves
  14. MockJS和Easy Mock使用
  15. Phonics 自然拼读法 g, o, u, l, f, b Teacher:Lamb
  16. android java 字符串正则表达式 分离特殊字符串
  17. Flume采集Nginx日志到HDFS
  18. Codeforces 374D - Inna and Sequence
  19. (转)c#反射
  20. ARG102E:Stop. Otherwise...

热门文章

  1. HDU - 5036 Explosion
  2. 图片组件——axure线框图部件库介绍
  3. 嵌入式ntp服务器的移植
  4. Head First PHP &amp;amp;MySQL学习笔记
  5. 设计模式6:Composite
  6. 使用hadoop ecipse插件须要注意的问题
  7. Mac AppStore 登陆提示 未知错误
  8. 【Java数据结构】Java数据结构之链表反转
  9. vc 加载bmp位图并显示的方法
  10. Delphi 获取网站验证码的图片