用tarjan缩点 
然后用dfn[u] < low[v]缩点并且保存起来 
在sort一遍输出

 #include<stdio.h>
#include<string.h>
#include<algorithm> using namespace std; const int maxn = ; struct Node {
int u;
int v;
int next;
};
struct Edge{
int u;
int v;
};
Edge edge[maxn];
Node node[maxn * ];
int head[maxn];
int dfn[maxn];
int low[maxn];
int fath[maxn];
bool vis[maxn];
bool maps[maxn][maxn];
int n, tol, cnt; void init() {
cnt = tol= ;
memset(dfn, , sizeof(dfn));
memset(low, , sizeof(low));
memset(maps, , sizeof(maps));
memset(fath, , sizeof(fath));
memset(head, -, sizeof(head));
memset(vis, false, sizeof(vis));
} void addnode(int u, int v) {
node[tol].u = u;
node[tol].v = v;
node[tol].next = head[u];
head[u] = tol++;
} void dfs(int u, int fa){
fath[u] = fa;
low[u] = dfn[u] = ++cnt;
vis[u] = true;
for(int i=head[u]; i!=-; i=node[i].next) {
int v = node[i].v;
if(!dfn[v]) {
dfs(v, u);
low[u] = min(low[u], low[v]);
} else if(v != fa) {
low[u] = min(low[u], dfn[v]);
}
}
} void tarjan() {
for(int u=; u<n; u++) {
if(!dfn[u]) {
dfs(u, u);
}
}
} bool cmp(Edge a, Edge b) {
if(a.u == b.u)
return a.v < b.v;
else
return a.u < b.u;
} void solve() {
tol = ;
for(int u=; u<n; u++) {
int v = fath[u];
if(low[u] > dfn[v] && v != u) {
edge[tol].u = u;
edge[tol].v = v;
if(edge[tol].u > edge[tol].v)
swap(edge[tol].u, edge[tol].v);
tol++;
}
}
sort(edge, edge+tol, cmp);
printf("%d critical links\n", tol);
for(int i=; i<tol; i++) {
printf("%d - %d\n", edge[i].u, edge[i].v);
}
printf("\n");
} int main() {
while(scanf("%d", &n) != EOF) {
init();
if(n == ) {
printf("0 critical links\n\n");
continue;
}
for(int i=; i<=n; i++) {
int u;
int num;
scanf("%d (%d)", &u, &num);
for(int j=; j<=num; j++) {
int v;
scanf("%d", &v);
maps[u][v] = maps[v][u] = ;
}
}
for(int i=; i<n; i++) {
for(int j=i+; j<n; j++) {
if(maps[i][j]) {
addnode(i, j);
addnode(j, i);
}
}
}
tarjan();
solve();
}
return ;
}

最新文章

  1. Python之路-python(堡垒机)
  2. 使用autolayout,设置子控件的宽度 与父视图的宽度成比例大小(这样类似可以设置多个按钮平均横屏排列)
  3. Jquery省市区三级联动案例
  4. Windows下gvim配置
  5. Maven工程中的右键team
  6. 如何让DevExpress TreeList的每个结点高亮显示?
  7. IEEE754测试-软件
  8. WEB程序会话管理--HttpSession和Cookie
  9. Max Sum (hdu 1003 简单DP水过)
  10. 关于SVN工具的配置及使用
  11. chrome调试技巧
  12. python︱字符操作杂记(split、zip...)
  13. HMM:隐马尔科夫模型-维特比算法
  14. 【OpenGL】【计算机图形学原理】撸课本系列一
  15. unity-----------------------四元数与欧拉旋转方法
  16. hive的安装,一般不容易察觉的hdfs的配置问题导致hive安装的失败
  17. 【转】iOS:AvPlayer设置播放速度不生效的解决办法
  18. HDU2043 密码
  19. java网络编程TCP传输—流操作—拿到源后的写入动作
  20. python发布包流程

热门文章

  1. PAT L2-013 红色警报
  2. C#设计模式之5:简单工厂和工厂方法模式
  3. Lumen与laravel的区别
  4. API知识点总结
  5. 【转】MySQL sql_mode 说明(及处理一起 sql_mode 引发的问题)
  6. 引入kaptcha实现验证码验证
  7. Python OpenCV人脸识别案例
  8. C-Lodop设置页面一加载就打印
  9. Vue-router的API详解
  10. Xtoken