P2746-[USACO5.3]校园网Network of Schools

  1 #include <bits/stdc++.h>
  2 
  3 using namespace std;
  4 #define _for(i,a,b) for(int i = (a);i < b;i ++)
  5 #define _rep(i,a,b) for(int i = (a);i > b;i --)
  6 #define INF 0x3f3f3f3f
  7 #define pb push_back
  8 #define maxn 500
  9 typedef long long ll;
 10 inline ll read()
 11 {
 12     ll ans = 0;
 13     char ch = getchar(), last = ' ';
 14     while(!isdigit(ch)) last = ch, ch = getchar();
 15     while(isdigit(ch)) ans = (ans << 1) + (ans << 3) + ch - '0', ch = getchar();
 16     if(last == '-') ans = -ans;
 17     return ans;
 18 }
 19 inline void write(ll x)
 20 {
 21     if(x < 0) x = -x, putchar('-');
 22     if(x >= 10) write(x / 10);
 23     putchar(x % 10 + '0');
 24 }
 25 vector<int> G[maxn];
 26 vector<int> rG[maxn];
 27 vector<int> vs;
 28 vector<int> ans[maxn];
 29 vector<int> G2[maxn];
 30 map<int,int> m;
 31 bool vis[maxn];
 32 bool used[maxn];
 33 int V,E;
 34 int k = 0;
 35 void add_edge(int from,int to)
 36 {
 37     G[from].pb(to);
 38     rG[to].pb(from);
 39 }
 40 void dfs(int v)
 41 {
 42     used[v] = true;
 43     _for(i,0,G[v].size())
 44     if(!used[G[v][i]])
 45         dfs(G[v][i]);
 46     vs.pb(v);
 47 }
 48 void rdfs(int v,int k)
 49 {
 50     used[v] = true;
 51     m[v] = k;
 52     ans[k].pb(v);
 53     _for(i,0,rG[v].size())
 54     if(!used[rG[v][i]])
 55         rdfs(rG[v][i],k);
 56 }
 57 //第k个集合里有哪些节点 ans[k]
 58 //rnt为最大集合的集合大小
 59 void Kosaraju()
 60 {
 61     memset(used,0,sizeof(used));
 62     _for(v,1,V+1)
 63     if(!used[v])
 64         dfs(v);
 65 
 66     memset(used,0,sizeof(used));
 67     
 68     _rep(i,vs.size()-1,-1)
 69     if(!used[vs[i]])
 70     {
 71         rdfs(vs[i],k);
 72         k ++;
 73     }
 74 }
 75 int in = 0,out = 0;
 76 int ans1 = 0,ans2 = 0;
 77 void solve()
 78 {
 79     int a[maxn];
 80     memset(a,0,sizeof(a));
 81     _for(i,0,k)
 82     {
 83         if(!G2[i].size())
 84             out ++;
 85         _for(j,0,G2[i].size())
 86         {
 87             a[G2[i][j]] ++;
 88         }
 89     }
 90     _for(i,0,k)
 91         if(!a[i])
 92             in ++;
 93     ans1 = in;
 94     ans2 = max(in,out);
 95     if(k==1)
 96         ans2 = 0;
 97 }
 98 int main()
 99 {
100     V = read();
101     _for(i,1,V+1)
102     {
103         int t = read();
104         while(t)
105         {
106             add_edge(i,t);
107             t = read();
108         }
109     }
110     Kosaraju();
111 
112     _for(i,1,V+1)
113     {
114         if(!vis[i])
115         {
116             int nwbl = m[i];
117             int sz = ans[nwbl].size();
118             _for(j,0,sz)
119             {
120                 vis[ans[nwbl][j]] = 1;
121                 _for(k,0,G[ans[nwbl][j]].size())
122                     if(nwbl!=m[G[ans[nwbl][j]][k]])
123                         G2[nwbl].pb(m[G[ans[nwbl][j]][k]]);
124             }
125         }
126     }
127     solve();
128     printf("%d
%d
",ans1,ans2);
129     return 0;
130 }