796 Critical Links(무방향 다이어그램의 브리지 - 템플릿 필요)
코드:
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
using namespace std;
const int N = 110;
int n, ans, g[N][N];
int dfs_clock, pre[N], low[N];
bool is[N][N];
int dfs( int u, int fa )
{
int lowu = pre[u] = ++dfs_clock;
int child = 0;
for ( int v = 0; v < n; ++v ) if ( g[u][v] ) {
if ( !pre[v] ) {
child++;
int lowv = dfs( v, u );
lowu = min( lowu, lowv );
if ( lowv > pre[u] ) {
if ( !is[u][v] && !is[v][u] ) {
ans++;
is[u][v] = is[v][u] = 1;
}
}
}
else if ( pre[v] < pre[u] && v != fa ) lowu = min( pre[v], lowu );
}
low[u] = lowu;
return lowu;
}
int main()
{
while ( scanf("%d", &n) != EOF ) {
memset(g, 0, sizeof(g));
memset(pre, 0, sizeof(pre));
memset(is, 0, sizeof(is));
ans = dfs_clock = 0;
for ( int i = 0; i < n; ++i ) {
int u, v, num;
scanf("%d (%d)", &u, &num);
while ( num-- ) {
scanf("%d", &v);
g[u][v] = g[v][u] = 1;
}
}
for ( int i = 0; i < n; ++i ) if ( !pre[i] ) dfs(i, -1);
printf("%d critical links
", ans);
for ( int i = 0; i < n; ++i )
for ( int j = i+1; j < n; ++j )
if ( is[i][j] ) printf("%d - %d
", i, j);
printf("
");
}
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.