Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

*****************************注意只有一个连通块时输出1 0***********************

Posted by lz1 at 2012-02-13 20:43:15 on Problem 1236
#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:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator