洛谷 P2746 [USACO5.3]校园网 Network of Schools 题解

Tarjan 模板题

第一问就是缩点之后看有多少个入度为零的点就好了。

第二问是在缩点后将每个点的入度和出度都求出（只要有入度或出度就置为1），然后比较哪个有值的多，将多的作为答案输出。原因是由题可得，要使缩完的点也构成一个强连通分

量，即入度和出度都大于等于1。

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 #define maxn 10010

 using namespace std;

 inline int read()

 {

     int x=;

     bool f=;

     char c=getchar();

     for(; !isdigit(c); c=getchar()) if(c=='-') f=;

     for(; isdigit(c); c=getchar()) x=(x<<)+(x<<)+c-'';

     if(f) return x;

     return -x;

 }

 inline void write(int x)

 {

     if(x<){putchar('-');x=-x;}

     if(x>)write(x/);

     putchar(x%+'');

 }

 struct node

 {

     int v,nex;

 }edge[maxn];

 int n,cnt,inl,top,res1,res2,num,cd2,rd2;

 int head[maxn],st[maxn],low[maxn],dfn[maxn],inn[maxn],si[maxn],rd[maxn],cd[maxn];

 inline void add(int x,int y)

 {

     cnt++;

     edge[cnt].v=y;

     edge[cnt].nex=head[x];

     head[x]=cnt;

 }

 inline void Tarjan(int from)

 {

     dfn[from]=low[from]=++num;

     st[++top]=from;

     for(int i=head[from];i!=-;i=edge[i].nex)

     {

         int to=edge[i].v;

         if(!dfn[to])

         {

             Tarjan(to);

             low[from]=min(low[from],low[to]);

         }

         else if(!inn[to])

             low[from]=min(low[from],dfn[to]);

     }

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

     {

         inn[from]=++inl;

         ++si[inl];

         while(st[top]!=from)

         {

             ++si[inl];

             inn[st[top]]=inl;

             --top;

         }

         --top;

     }

 }

 int main()

 {

     memset(head,-,sizeof(head));

     n=read();

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

     {

         int x;

         while()

         {

             x=read();

             if(x!=)add(i,x);

             else break;

         }

     }

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

         if(!dfn[i])

             Tarjan(i);

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

        for(int j=head[i];j!=-;j=edge[j].nex)

        {

             if(inn[i]!=inn[edge[j].v])

             {

                 rd[inn[edge[j].v]]++;

                 cd[inn[i]]++;

             }

        }

     if(inl==)

     {

         cout<<<<endl<<;

         return ;

     }

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

         if(rd[i]==)

             res1++;

     write(res1);

     cout<<endl;

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

     {

         if(cd[i]==)

             cd2++;

         if(rd[i]==)

             rd2++;

     }

     res2=max(cd2,rd2);

     write(res2);

     return ;

 }

请各位大佬斧正