usaco 校园网

题解：

显然当一个图上的点是一个环时能满足题目要求

那么我们来考虑怎么形成一个环

很显然的是要先缩点

缩完点就成为了森林，如何让森林成环呢？

考虑一下环上的点的入度出度一定都大于1

而连一条边可以增加某个点的入度和某个点的出度

问题就变成了求入度为0或者出度为0的最大值

代码：

#include <bits/stdc++.h>

#define rint register int

#define IL inline

#define rep(i,h,t) for (int i=h;i<=t;i++)

#define dep(i,t,h) for (int i=t;i>=h;i--)

using namespace std;

const int N=3e5;

struct re{

  int a,b,from;

}e[N*];

int head[N],col[N],cd[N],rd[N],l,n;

bool ins[N];

void arr(int x,int y)

{

  e[++l].a=head[x];

  e[l].b=y;

  e[l].from=x;

  head[x]=l;

}

stack<int> S;

int cnt,color,dfn[N],low[N];

void tarjan(int x)

{

  S.push(x); dfn[x]=low[x]=++cnt; ins[x]=;

  for (rint u=head[x];u;u=e[u].a)

  {

    int v=e[u].b;

    if (!dfn[v])

    {

      tarjan(v);

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

    }

    if (ins[v]) dfn[x]=min(dfn[x],dfn[v]);

  }

  if (low[x]==dfn[x])

  {

    color++;

    while ()

    {

      int y=S.top(); S.pop(); ins[y]=;

      col[y]=color;

      if (y==x) break;

    }

  }

}

int main()

{

    freopen("1.in","r",stdin);

    freopen("1.out","w",stdout);

    ios::sync_with_stdio(false);

    cin>>n;

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

    {

        while (true)

        {

          int x;

          cin>>x;

          if (x) arr(i,x); else break;

        }

    }

    int rdans=,cdans=;

    for (int i=;i<=n;i++) if (!dfn[i]) tarjan(i);

    if (color==) cout<<<<endl<<;

    else{

        for (int i=;i<=l;i++)

          if (col[e[i].b]!=col[e[i].from])

            rd[col[e[i].b]]++,cd[col[e[i].from]]++;

        for (int i=;i<=color;i++)

        {

            if (!rd[i]) rdans++;

            if (!cd[i]) cdans++;

        }

        cout<<rdans<<endl<<max(rdans,cdans);

  }

}

#include <bits/stdc++.h>

using namespace std;

int n,x,l;

#define maxn 100000

struct re{

    int a,b,from;

}a[maxn];

int color,dfn[maxn],low[maxn],col[maxn];

int rdans,cdans,head[maxn],now,rd[maxn],cd[maxn];

bool ins[maxn];

int arr(int x,int y)

{

    a[++l].a=head[x];

    a[l].b=y;

    a[l].from=x;

    head[x]=l;

}

stack <int> s;

void tarjan(int x)

{

    dfn[x]=low[x]=++now;

    int u=head[x];

    s.push(x); ins[x]=;

    while (u)

    {

        int v=a[u].b;

        if (!dfn[v])

        {

            tarjan(v);

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

        }

        if (ins[v]) low[x]=min(low[x],dfn[v]);

        u=a[u].a;

    }

    if (dfn[x]==low[x])

    {

        color++;

        while (true)

        {

            int y=s.top();

            col[y]=color;

            s.pop();

            ins[y]=;

            if (y==x) break;

        }

    }

}

int main()

{

    freopen("noip.in","r",stdin);

    freopen("noip.out","w",stdout);

    cin>>n;

    memset(ins,,sizeof(ins));

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

    {

        while (true)

        {

          cin>>x;

          if (x) arr(i,x); else break;

        }

    }

    for (int i=;i<=n;i++) if (!dfn[i]) tarjan(i);

    if (color==) cout<<<<endl<<;

    else{

        for (int i=;i<=l;i++)

          if (col[a[i].b]!=col[a[i].from])

            rd[col[a[i].b]]++,cd[col[a[i].from]]++;

        for (int i=;i<=color;i++)

        {

            if (!rd[i]) rdans++;

            if (!cd[i]) cdans++;

        }

        cout<<rdans<<endl<<max(rdans,cdans);

  }

}