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

Tarjan 模板题

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

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

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

  1 #include<iostream>
  2 #include<cstdio>
  3 #include<cstring>
  4 #include<algorithm>
  5 #define maxn 10010
  6 using namespace std;
  7 inline int read() 
  8 {
  9     int x=0;
 10     bool f=1;
 11     char c=getchar();
 12     for(; !isdigit(c); c=getchar()) if(c=='-') f=0;
 13     for(; isdigit(c); c=getchar()) x=(x<<3)+(x<<1)+c-'0';
 14     if(f) return x;
 15     return 0-x;
 16 }
 17 inline void write(int x)
 18 {
 19     if(x<0){putchar('-');x=-x;}
 20     if(x>9)write(x/10);
 21     putchar(x%10+'0');
 22 }
 23 struct node
 24 {
 25     int v,nex;
 26 }edge[maxn];
 27 int n,cnt,inl,top,res1,res2,num,cd2,rd2;
 28 int head[maxn],st[maxn],low[maxn],dfn[maxn],inn[maxn],si[maxn],rd[maxn],cd[maxn];
 29 inline void add(int x,int y)
 30 {
 31     cnt++;
 32     edge[cnt].v=y;
 33     edge[cnt].nex=head[x];
 34     head[x]=cnt;
 35 }
 36 inline void Tarjan(int from) 
 37 {
 38     dfn[from]=low[from]=++num;
 39     st[++top]=from;
 40     for(int i=head[from];i!=-1;i=edge[i].nex)
 41     {
 42         int to=edge[i].v;
 43         if(!dfn[to])
 44         {
 45             Tarjan(to);
 46             low[from]=min(low[from],low[to]);
 47         }
 48         else if(!inn[to])
 49             low[from]=min(low[from],dfn[to]);
 50     }
 51     if(low[from]==dfn[from])
 52     {
 53         inn[from]=++inl;
 54         ++si[inl]; 
 55         while(st[top]!=from)
 56         {
 57             ++si[inl];
 58             inn[st[top]]=inl;
 59             --top;
 60         }
 61         --top;
 62     }
 63 }
 64 int main()
 65 {
 66     memset(head,-1,sizeof(head));
 67     n=read();
 68     for(int i=1;i<=n;i++)
 69     {
 70         int x;
 71         while(1)
 72         {
 73             x=read();
 74             if(x!=0)add(i,x);
 75             else break;
 76         }
 77     }
 78     for(int i=1;i<=n;i++)
 79         if(!dfn[i])
 80             Tarjan(i);
 81     for(int i=1;i<=n;i++)
 82        for(int j=head[i];j!=-1;j=edge[j].nex)
 83        {
 84             if(inn[i]!=inn[edge[j].v])
 85             {
 86                 rd[inn[edge[j].v]]++;
 87                 cd[inn[i]]++;
 88             }
 89 
 90        }
 91     if(inl==1)
 92     {
 93         cout<<1<<endl<<0;
 94         return 0;
 95     }
 96     for(int i=1;i<=inl;i++)
 97         if(rd[i]==0)
 98             res1++;
 99     write(res1);
100     cout<<endl;
101     for(int i=1;i<=inl;i++)
102     {
103         if(cd[i]==0)
104             cd2++;
105         if(rd[i]==0)
106             rd2++;
107     }
108     res2=max(cd2,rd2);
109     write(res2);
110     return 0;
111 }

请各位大佬斧正（反正我不认识斧正是什么意思）