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

Dear 丶 2023-06-01 08:57 19阅读 0赞

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\n%d\n",ans1,ans2);
    129     return 0;
    130 }

转载于:https://www.cnblogs.com/Asurudo/p/11607855.html