LA 4287 有相图的强连通分量

时间：2024-07-29 14:33:50

大白书P322 , 一个有向图在添加至少的边使得整个图变成强连通图， 是计算整个图有a个点没有 入度， b 个点没有出度， 答案为 max(a,b) ; 至今不知所云。（求教）

#include <iostream>

#include <vector>

#include <stack>

#include <cstdio>

#include <string.h>

using namespace std;

const int maxn = +;

vector<int> G[maxn];

int pre[maxn], lowlink[maxn],sccno[maxn],dfs_clock, scc_cnt;

stack<int>S;

void dfs(int u){

     pre[u] = lowlink[u] = ++dfs_clock;

     S.push(u);

     for(int i=; i<G[u].size(); i++){

           int v = G[u][i];

           if(!pre[v]){

               dfs(v);

               lowlink[u]=min(lowlink[u],lowlink[v]);

           }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;

         }

     }

}

void find_scc(int n){

     dfs_clock = scc_cnt =;

     memset(sccno,,sizeof(sccno));

     memset(pre,,sizeof(pre));

     for(int i=; i<n; i++)

        if(!pre[i]) dfs(i);

}

int in0[maxn],out0[maxn];

int main()

{

     int T,n,m;

     scanf("%d",&T);

     while(T--){

        scanf("%d%d",&n,&m);

         for(int i=; i<n; i++)G[i].clear();

         for(int i=; i<m ; i++){

              int u,v;

              scanf("%d%d",&u,&v); u--;v--;

                G[u].push_back(v);

         }

         find_scc(n);

         for(int i=; i<=scc_cnt; ++i ) in0[i] = out0[i] =;

         for(int u=; u<n; u++)

         for(int i=; i<G[u].size(); i++){

            int v = G[u][i];

            if(sccno[u] != sccno[v] ) in0[sccno[v]]=out0[sccno[u]] =;

         }

         int a=, b=;

         for(int i=; i<=scc_cnt; i++){

              if(in0[i]) a++;

              if(out0[i]) b++;

         }

         int ans= max(a,b);

         if(scc_cnt == ) ans=;

         printf("%d\n",ans);

     }

    return ;

}

相关文章