| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
*****************************注意只有一个连通块时输出1 0***********************#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
using namespace std;
/*
题目大意:网络中的一学校可以将软件发送给其他一些学校,能够发送给谁取决于他们各自维护的一个清
单。将学校看成一个节点,给出每个学校的维护清单,问至少需要复制几次软件,使毎个学校都能够得
到该软件,在清单中至少添加几项,可使软件至少复制一次,所有学校都可以得到。
思路:
1、用Tarjan算法求出强连通分分量。2、缩点重新构图。3、分别求节点的出度和入度。
第一个问题就是出度为0的个数,第二问题就是出度和入度为0个数中的较大者。
代码如下:
*/
#define MAX_N 110
#define MAX_M 11000
#define insert(a, b) (e[++m].s = (a), e[m].t = (b), e[m].n = fi[(a)], fi[(a)] = m)
struct node { int s, t, n; };
node e[MAX_M];
int ind[MAX_N], oud[MAX_N];
int dfn[MAX_N], low[MAX_N], belong[MAX_N];
int fi[MAX_N], stack[MAX_N];
bool in[MAX_N];
int n, m, top, s1, s2, tot, tim;
void dfs(int x)
{
dfn[x] = low[x] = ++tot;
stack[++top] = x, in[x] = true;
for (int i = fi[x]; i != -1; i = e[i].n)
{
int t = e[i].t;
if (!dfn[t])
{
dfs (t);
if (low[t] < low[x]) low[x] = low[t];
}
else if (in[t] && dfn[t] < low[x])
low[x] = dfn[t];
}
if (dfn[x] == low[x])
while (stack[top + 1] != x)
belong[stack[top]] = x, in[stack[top--]] = false;
}
int main(void)
{
freopen ("1236.in", "r", stdin);
freopen ("1236.out", "w", stdout);
while (scanf ("%d", &n) != EOF)
{
memset (fi, -1, sizeof (fi));
memset (dfn, 0, sizeof (dfn));
memset (ind, 0, sizeof (ind));
memset (oud, 0, sizeof (oud));
m = s1 = s2 = 0;
for (int i = 1; i <= n; i++)
{
int x = 0;
while (scanf ("%d", &x) != EOF && x != 0)
insert (i, x);
}
/*for (int i = 1; i <= n; i++)
for (int j = fi[i]; j != -1; j = e[j].n)
printf ("%d %d\n", i, e[j].t);*/
for (int i = 1; i <= n; i++)
if (!dfn[i]) top = 0, dfs (i);
for (int i = 1; i <= m; i++)
if (belong[e[i].s] != belong[e[i].t])
ind[belong[e[i].t]]++, oud[belong[e[i].s]]++;
for (int i = 1; i <= n; i++)
{
if (i != belong[i]) continue;
tim++;
if (ind[belong[i]] == 0) s1++;
if (oud[belong[i]] == 0) s2++;
}
/* for (int i = 1; i <= n; i++)
printf ("%d -> %d\n", i, belong[i]);*/
printf ("%d\n", s1);
if (tim == 1) puts ("0");
else printf ("%d\n", max (s1, s2));
}
return 0;
}
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator