POJ 1236 Network of Schools 強接通分量

tags:    時間:2014-03-23 19:21:07
POJ 1236 Network of Schools 強連通分量

鏈接:http://poj.org/problem?id=1236

題意:提供一個路徑為單向的校園網路,給出兩個任務,第一個是至少要多少台電腦接受新軟體才能讓信息傳遍整個校園網路,第二個是任務是問至少要加多少條邊讓多少點都彼此相通。

思路:第一個是求入度為零的強連通分量,第二個答案是入度為零的強連通分量數和出度為零的強連通分量數更大的那個。(tarjan的思路看看書,模板網上漫天飄!)

代碼:

#include <iostream> #include <cstdio> #include <cstring> #include <cctype> #include <cstdlib> #include <cmath> #include <map> #include <set> #include <queue> #include <stack> #include <vector> #include <ctype.h> #include <algorithm> #include <string> #define PI acos(-1.0) #define maxn 105 #define INF 1<<25 #define MAX 0x7fffffff #define mem(a,b) memset(a,b,sizeof(a)) #define f(i,a,b) for(i=a;i<b;i++) typedef long long ll; using namespace std; struct Edge {     int v;     int next; } edge[maxn*maxn]; int head[maxn],dfn[maxn],low[maxn],belong[maxn],instack[maxn],in[maxn],ou[maxn]; int tt,top,cnt,v,A,B; int add_edge(int u,int v) {     edge[top].v=v;     edge[top].next=head[u];     head[u]=top++; } stack <int> S; int init() {     mem(head,-1);     mem(dfn,0);     mem(low,0);     mem(belong,0);     mem(instack,0);     mem(in,0);     mem(ou,0);     A=B=top=cnt=tt=0; } int tarjan(int u) {     dfn[u]=low[u]=++cnt;     S.push(u);     instack[u]=1;     for(int i=head[u]; i!=-1; i=edge[i].next)     {         int v=edge[i].v;         if(!dfn[v])         {             tarjan(v);             low[u]=min(low[u],low[v]);         }         else if(instack[v]&&dfn[v]<low[u])             low[u]=dfn[v];     }     if(dfn[u]==low[u])     {         tt++;         do         {             v=S.top();             instack[v]=0;             belong[v]=tt;             S.pop();         }         while(v!=u);     } } int main() {     int tot,i;     scanf("%d",&tot);     init();     f(i,1,tot+1)     {         int x;         while(scanf("%d",&x))         {             if(!x)                 break;             else add_edge(i,x);         }     }     f(i,1,tot+1)     if(!dfn[i])         tarjan(i);     f(i,1,tot+1)     {         int a=belong[i];         for(int j=head[i]; j!=-1; j=edge[j].next)         {             int b=belong[edge[j].v];             if(a!=b)             {                 in[b]++;                 ou[a]++;             }         }     }     if(tt==1)     {         printf("1\n");         printf("0\n");     }     else     {         f(i,1,tt+1)         {             if(!in[i])                 A++;             if(!ou[i])                 B++;         }         printf("%d\n",A);         printf("%d\n",max(A,B));     } }


推薦閱讀文章

Bookmark the permalink ,來源:互聯網