題意是給出一個連通圖, 問如果切斷任何一條邊仍使圖是連通的話至少要加幾條邊.
于是求關鍵邊, 關鍵邊連成一棵樹, 易證在葉子處連邊是最優的.
在網上看了幾篇這題的代碼, 都說成求塊或者求重連通分量, 其實是錯的, 重連通分量隻跟關鍵點有關, 而這題要的是關鍵邊, 隻能說是資料太弱了.
#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