UVA 796 Critical Links

输出桥。

#include<cstdio>
#include<cstring>
#include<cmath>
#include<vector>
#include<algorithm>
using namespace std; const int maxn = + ;
const int Maxn = * + ;
int low[maxn];
int dfn[maxn];
int U[maxn], V[maxn]; struct Edge
{
int from, to, id, ans;
} edge[Maxn];
vector<int>G[maxn];
int N, M;
int tmpdfn;
int tot;
int Start, End; struct ANSS
{
int first, second;
}ANS[Maxn]; void init()
{
for (int i = ; i<maxn; i++) G[i].clear();
memset(low, , sizeof(low));
memset(dfn, , sizeof(dfn));
low[] = dfn[] = ;
tmpdfn = ;
tot = ;
} void AddEdge(int u, int v)
{
edge[tot].from = u;
edge[tot].to = v;
edge[tot].id = tot;
edge[tot].ans = ;
G[u].push_back(tot);
tot++; edge[tot].from = v;
edge[tot].to = u;
edge[tot].id = tot;
edge[tot].ans = ;
G[v].push_back(tot);
tot++; } int Tarjan(int u, int id)
{
tmpdfn++;
int lowu = dfn[u] = tmpdfn;
for (int i = ; i<G[u].size(); i++)
{
int B = G[u][i];
if (!dfn[edge[B].to])
{
int lowv = Tarjan(edge[B].to, edge[B].id);
lowu = min(lowu, lowv);
if (lowv >= dfn[u])
{
if (lowv>dfn[u])
edge[B].ans = ;
}
}
else if (dfn[edge[B].to])
{
if (edge[B].id / == id / ) continue;
lowu = min(lowu, dfn[edge[B].to]);
}
} low[u] = lowu;
return lowu;
} bool cmp(const ANSS&a, const ANSS&b)
{
if (a.first == b.first) return a.second < b.second;
return a.first < b.first;
} void Display_Cutting_edge()
{
int AA = ;
for (int i = ; i < * M; i++)
{
if (edge[i].ans)
{
if (edge[i].from < edge[i].to)
{
ANS[AA].first = edge[i].from;
ANS[AA].second = edge[i].to;
}
else
{
ANS[AA].first = edge[i].to;
ANS[AA].second = edge[i].from;
}
AA++;
}
}
printf("%d critical links\n", AA);
sort(ANS, ANS + AA, cmp);
for (int i = ; i < AA; i++)
printf("%d - %d\n", ANS[i].first-, ANS[i].second-);
printf("\n");
} int main()
{
while (~scanf("%d", &N))
{
init();
M = ;
for (int i = ; i <= N; i++)
{
int from,TTT;
scanf("%d (%d)", &from, &TTT);
while (TTT--)
{
int too;
scanf("%d", &too);
if (from >= too) continue;
U[M] = from + ; V[M] = too + ;
AddEdge(U[M], V[M]);
M++;
}
}
Start = ; End = N;
Tarjan(, -);
for (int i = ; i <= N; i++) if (!dfn[i]) Tarjan(i, -);
Display_Cutting_edge();
}
return ;
}
上一篇:第36.3节 动画-路径动画生成要点


下一篇:塔吊模拟