【POJ 1236 Network of Schools】强联通分量问题 Tarjan算法，缩点

题目链接：http://poj.org/problem?id=1236

题意：给定一个表示n所学校网络连通关系的有向图。现要通过网络分发软件，规则是：若顶点u,v存在通路，发给u，则v可以通过网络从u接收到。

现要求解两个问题：

TaskA: 最少分发给几个学校，就可以使所有的学校都能得到软件。

TaskB: 最少增加几条边，就可以使得，发软件给任一学校，所有学校都可以收到。

思路：先进行强联通分量分解，然后缩点，并计算缩点后每个点的出度、入度。入度为0的点的总数为 a ，出度为0的点总数为 b。a即TaskA的答案，而TaskB的答案为max(a, b)。

求SCC部分参考了 http://blog.csdn.net/dgq8211/article/details/7834292

缩点的做法很暴力，将每个强联通分量重新编号为一个集合，在求SCC时记录belong。

 #include <cstdio>

 #include <vector>

 #include <stack>

 #include <cstring>

 using namespace std;

 const int MAX_N = ;

 int n;

 vector<int> G[MAX_N];

 stack<int> S;

 int clock;

 int scc;

 int dfn[MAX_N], low[MAX_N];

 int inStack[MAX_N];

 int belong[MAX_N];

 int indeg[MAX_N];//scc的

 int outdeg[MAX_N];

 void init(){

     scc = ;

     clock = ;

     memset(dfn, , sizeof(dfn));

     memset(low, , sizeof(low));

     memset(inStack, , sizeof(inStack));

     memset(indeg, , sizeof(indeg));

     memset(outdeg, , sizeof(outdeg));

 }

 void tarjan(int u){

     dfn[u] = low[u] = ++clock;

     S.push(u);

     inStack[u] = ;

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

         int v = G[u][i];

         if(!dfn[v]){

             tarjan(v);

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

         }else if(inStack[v]){

             low[u] = min(low[u], dfn[v]);

         }

     }

     if(dfn[u] == low[u]){

         int v;

         do{

             v = S.top();

             S.pop();

             inStack[v] = ;

             belong[v] = scc;

             //printf("%d ", v);

         }while(v != u);

         scc++;

     }

 }

 int main()

 {

     freopen("1236.txt", "r", stdin);

     scanf("%d", &n);

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

         int u;

         while(scanf("%d", &u) && u){

             G[i].push_back(u);

             //outdeg[i]++;

             //indeg[u]++;

         }

     }

     init();

     for(int i=; i<=n; i++){//遍历所有点

         if(!dfn[i]){//未被发现的点

             tarjan(i);

         }

     }

     int a = ;

     int b = ;

     for(int i=; i<=n; i++){//缩点

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

             int u = G[i][j];

             if(belong[i] != belong[u]){

                 outdeg[belong[i]]++;

                 indeg[belong[u]]++;

             }

         }

     }

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

         if(indeg[i] == ) a++;

         if(outdeg[i] == ) b++;

     }

     b = max(a, b);

     if(scc == ) b = ;

     printf("%d\n%d\n", a, b);

     return ;

 }

巴特西

【POJ 1236 Network of Schools】强联通分量问题 Tarjan算法，缩点

最新文章

热门文章