Light OJ 1026 - Critical Links (图论-双向图tarjan求割边,桥)

题目大意:双向联通图, 现在求减少任意一边使图的联通性改变,按照起点从小到大列出所有这样的边

解题思路:双向边模版题 tarjan算法

代码如下:

#include<bits/stdc++.h>
using namespace std; const int N = ;
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 = ; i < vec[u].size(); ++ i)
{
int v = vec[u][i];
if(dfn[v] == -)
{
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 = ; i < N; ++ i)
vec[i].clear(); int n;
scanf("%d", &n); for(int i = ; i < n; ++ i)
{
int a, b, c;
scanf("%d (%d)", &a, &b);
for(int j = ; j <= b; ++ j)
{
scanf("%d", &c);
vec[a].push_back(c);
}
} memset(dfn, -, sizeof(dfn));
memset(low, -, sizeof(low)); ans = res = ;
for(int i = ; i < n; ++ i)
{
if(dfn[i] == -)
tarjan(i, -);
}
sort(edge, edge+ans);
printf("Case %d:\n", cases);
printf("%d critical links\n", ans);
for(int i=; i<ans; ++ i)
printf("%d - %d\n", edge[i].first, edge[i].second);
} int main()
{
int T;
scanf("%d", &T);
for(int i = ; i <= T; ++ i)
solve(i);
return ;
}
上一篇:Linux设置环境变量小结:设置永久变量&临时变量 全局变量&局部变量


下一篇:IntelliJ Idea解决Could not autowire. No beans of 'xxxx' type found的错误提示