首页 > 代码库 > Light OJ 1026 - Critical Links (图论-求割边, 桥)
Light OJ 1026 - Critical Links (图论-求割边, 桥)
题目大意:双向联通图, 现在求减少任意一边使图的联通性改变,按照起点从小到大列出所有这样的边
解题思路:双向边模版题 tarjan算法
代码如下:
#include<bits/stdc++.h>using namespace std;const int N = 100003;vector<int>vec[N];pair<int, int>edge[N];int dfn[N], low[N];int res, ans;void tarjan(int u, int f){ dfn[u] = low[u] = res ++; for(int i = 0; i < vec[u].size(); ++ i) { int v = vec[u][i]; if(dfn[v] == -1) { tarjan(v, u); low[u] = min(low[u], low[v]); } else if(f != v) low[u] = min(low[u], dfn[v]); if(dfn[u] < low[v]) { if(u > v) edge[ans ++] = make_pair(v, u); else edge[ans ++] = make_pair(u, v); } }}void solve(int cases){ for(int i = 0; i < N; ++ i) vec[i].clear(); int n; scanf("%d", &n); for(int i = 0; i < n; ++ i) { int a, b, c; scanf("%d (%d)", &a, &b); for(int j = 1; j <= b; ++ j) { scanf("%d", &c); vec[a].push_back(c); } } memset(dfn, -1, sizeof(dfn)); memset(low, -1, sizeof(low)); ans = res = 0; for(int i = 0; i < n; ++ i) { if(dfn[i] == -1) tarjan(i, -1); } sort(edge, edge+ans); printf("Case %d:\n", cases); printf("%d critical links\n", ans); for(int i=0; i<ans; ++ i) printf("%d - %d\n", edge[i].first, edge[i].second);}int main(){ int T; scanf("%d", &T); for(int i = 1; i <= T; ++ i) solve(i); return 0;}
Light OJ 1026 - Critical Links (图论-求割边, 桥)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。