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

N(2<N<100)各學校之間有單向的網絡，每個學校得到一套軟件后，可以通過單向網絡向周邊的學校傳輸，問題1：初始至少需要向多少個學校發放軟件，使得網絡內所有的學校最終都能得到軟件。2，至少需要添加幾條傳輸線路(邊)，使任意向一個學校發放軟件后，經過若干次傳送，網絡內所有的學校最終都能得到軟件。

首先求出該圖所有的強連通分量，將其縮為一點，因為對于強連通分量，任意兩點都能互相可達，只要給DAG(強連通分量)中的任意一點都能互相到達。

縮點后然后統計每個點的入度與出度，入度為0的點肯定是A的答案，而對于答案B則是max(入度為0的點的個數，出度為0的點的個數)。B:入度為0我們只有給他一條路線入度+1能獲得軟件，出度同理。

View Code #include <iostream>
#include <cstdio>
#include <cstring>
#define maxn 107
using namespace std;
struct node
{
int v;
int next;
}g[maxn*maxn];
int low[maxn],dfn[maxn],head[maxn],stack[maxn],belong[maxn];
int in[maxn],out[maxn];
bool instack[maxn];
int bcnt,index,t,top,n;
void init()
{
memset(g,0,sizeof(g));
for (int i = 0; i < maxn; ++i)
{
head[i] = low[i] = dfn[i] =stack[i] = in[i] = out[i] = 0;
belong[i] = 0;
instack[i] = false;
}
t = 1;
index = bcnt = top = 0;
}
void add(int u,int v)
{
g[t].v = v;
g[t].next = head[u];
head[u] = t++;
}
void tarjan(int i)
{
int j,k;
low[i] = dfn[i] = ++index;
instack[i] = true;
stack[++top] = i;
for (k = head[i]; k; k = g[k].next)
{
j =g[k].v;
if (!dfn[j])
{
tarjan(j);
low[i] = min(low[i],low[j]);
}
else if(instack[j])
{
low[i] = min(low[i],dfn[j]);
}
}
if (dfn[i] == low[i])
{
bcnt++;
do
{
j = stack[top--];
instack[j] = false;
belong[j] = bcnt;
}while (j != i);
}
}
void solve()
{
for (int i = 1; i <= n; ++i)
{
if (!dfn[i])
tarjan(i);
}
for (int i = 1; i <= n; ++i)
{
//printf("~!!!%d\n",belong[i]);
for (int j = head[i]; j; j = g[j].next)
{
int k = g[j].v;
if (belong[k] != belong[i])
{
out[belong[i]]++;
in[belong[k]]++;
}
}
}
int ct1 = 0;
int ct2 = 0;
for (int i = 1; i <= bcnt; ++i)//這里要小于bcnt因為這是縮點后的
{
if (!in[i]) ct1++;
if (!out[i]) ct2++;
}
printf("%d\n",ct1);
if (bcnt == 1) printf("0\n");
else
printf("%d\n",max(ct1,ct2));
}
int main()
{
//freopen("d.txt","r",stdin);
int i,x;
while (cin>>n)
{
init();
for (i = 1; i <= n; ++i)
{
while (cin>>x)
{
if (!x) break;
add(i,x);
}
}
solve();
}
return 0;
}

總結

以上是生活随笔為你收集整理的pku 1236 Network of Schools (tarjan缩点)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。