这里延伸出一个题目 ， 给出一个有向图 ， 请问最小需要连接多少边才能让这个图变成强连通图 。
解法：先把图中的强连通分量都求出来 ， 然后再把每个强连通分量缩成一个点 ， 就能得到一个DAG图 ， 然后最小值 = max(a , b) ， a表示入度为0的点 ， b表示进度为0的点。
要注意的一点：当整个图就是一个强连通图时 ， 则需要增加的边为0；
代码：
#include
#include
#include
#include
#include
#include
using namespace std;
const int MAXN = 1000;
vectorgrap[MAXN] ;
int pre[MAXN] , lowlink[MAXN] , sccno[MAXN] , dfs_clock , scc_cnt;
stacks;
int n , m;
void init()
{
for(int i = 0 ; i <= n; i++)
grap[i].clear();
memset(pre , 0 , sizeof(pre));
memset(sccno , 0 , sizeof(sccno));
dfs_clock = scc_cnt = 0;
}
void dfs(int u)
{
pre[u] = lowlink[u] = ++dfs_clock;
s.push(u);
for(int i = 0 ; i < grap[u].size() ; i++)
{
int v = grap[u][i];
if(!pre[v])
{
dfs(v);
lowlink[u] = min(lowlink[v] , lowlink[u]);
}
else if(!sccno[v])
{
lowlink[u] = min(lowlink[u] , pre[v]) ;
}
}
if(lowlink[u] == pre[u])
{
scc_cnt++;
for(; 😉
{
int x = s.top() ; s.pop();
sccno[x] = scc_cnt;
if(x == u)
break;
}
}
}
int main()
{
while(scanf(“%d %d” , &n , &m) != EOF)
{
init();
int i , x , y;
for(i = 0 ; i < m; i++)
{
scanf(“%d %d” , &x , &y);
grap[x].push_back(y);
}
dfs(0);
int in0[MAXN] , out0[MAXN] ;
memset(in0 , 0 , sizeof(in0));
memset(out0 , 0 , sizeof(out0));
for(int u = 0 ; u < n ; u++)
for(int i = 0 ; i < grap[u].size() ; i++)
{
int v = grap[u][i] ;
if(sccno[u] != sccno[v])
in0[sccno[v]] = out0[sccno[u]] = 1;
}
int a = 0 , b = 0;
for(int i = 1; i <= scc_cnt ; i++)
{
if(!in0[i])
a++;
if(out0[i])
b++;
}
int ans = max(a , b);
if(scc_cnt == 1)
ans = 0;
printf(“%d\n” , ans);
}
return 0;
}