题意是给出一个连通图, 问如果切断任何一条边仍使图是连通的话至少要加几条边.
于是求关键边, 关键边连成一棵树, 易证在叶子处连边是最优的.
在网上看了几篇这题的代码, 都说成求块或者求重连通分量, 其实是错的, 重连通分量只跟关键点有关, 而这题要的是关键边, 只能说是数据太弱了.
#include < iostream >
#include < vector >
#define MAXN 1005
using namespace std;
vector < int > map[MAXN];
int dfn[MAXN], low[MAXN], deep, color[MAXN], com;
void dfs( int i, int f)
{
dfn[i] = low[i] = ++ deep;
for ( int j = 0 ; j < map[i].size(); j ++ )
{
int k = map[i][j];
if ( ! dfn[k])
{
dfs(k, i);
low[i] = min(low[i], low[k]);
}
else if (k != f)
low[i] = min(low[i], dfn[k]);
}
}
void set_color( int i)
{
for ( int j = 0 ; j < map[i].size(); j ++ )
{
int k = map[i][j];
if ( ! color[k])
{
if (low[k] > dfn[i]) color[k] = ++ com;
else color[k] = color[i];
set_color(k);
}
}
}
void biconnected( int n)
{
deep = 0 ;
dfs( 0 , - 1 );
com = 1 ;
color[ 0 ] = 1 ;
set_color( 0 );
}
int du[MAXN]; // 桥的度, 用来判叶子
int main()
{
int n, r, a, b;
scanf( " %d %d " , & n, & r);
while (r -- )
{
scanf( " %d %d " , & a, & b);
a -- ; b -- ;
map[a].push_back(b);
map[b].push_back(a);
}
biconnected(n);
for ( int i = 0 ; i < n; i ++ )
{
a = color[i];
for ( int j = 0 ; j < map[i].size(); j ++ )
{
b = color[map[i][j]];
if (a != b) du[a] ++ ;
}
}
int leap = 0 ;
for ( int i = 1 ; i <= com; i ++ )
if (du[i] == 1 )
leap ++ ;
printf( " %d\n " , (leap + 1 ) / 2 );
return 0 ;
}
转载于:https://www.cnblogs.com/lotus3x/archive/2008/09/07/1286171.html