很典型的求无向图的桥个数,并且输出
代码:
#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\n", ans); for ( int i = 0; i < n; ++i ) for ( int j = i+1; j < n; ++j ) if ( is[i][j] ) printf("%d - %d\n", i, j); printf("\n"); } }