洛谷P2921 [USACO08DEC]在农场万圣节Trick or Treat on the Farm

佚名 5年前 (2019-08-15) 算法 615人围观抢沙发百度已收录

题目链接：https://www.luogu.org/problem/P2921

思路：

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

这个题目我们可以先把强连通分量求出来，（强连通分量：在该子图中如果v->u，那么u->v一定成立）。

然后如果一个强连通分量的点数大于等于2，说明该强连通分量成环，而等于1的强连通分量，

要么自己成环，要么直接或间接连着一个环。

那么我们先用tarjan求强连通分量，然后处理下缩点后的有向无环图就好解决了。

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <cstring>
  4 #include <algorithm>
  5 #include <queue>
  6 #include <stack>
  7 #include <map>
  8 #include <cmath>
  9 #include <iomanip>
 10 using namespace std;
 11 
 12 typedef long long LL;
 13 #define inf (1LL << 25)
 14 #define rep(i,j,k) for(int i = (j); i <= (k); i++)
 15 #define rep__(i,j,k) for(int i = (j); i < (k); i++)
 16 #define per(i,j,k) for(int i = (j); i >= (k); i--)
 17 #define per__(i,j,k) for(int i = (j); i > (k); i--)
 18 
 19 const int N = 100010;
 20 int DFN[N];
 21 int LOW[N];
 22 bool insta[N];
 23 int sccno[N]; //NO.x 编号
 24 int sccdeep[N]; //分量深度
 25 int head[N];
 26 bool visscc[N]; //缩点后的有向无环图访问情况
 27 stack<int> sta;
 28 vector<int> scc[N];
 29 int scccnt,dfn,cnt;
 30 int n;
 31 
 32 struct Edge{
 33     int loc;
 34     int to;
 35     int next;
 36 }e[N];
 37 
 38 void add(int u,int v){
 39     e[cnt].loc = u;
 40     e[cnt].to = v;
 41     e[cnt].next = head[u];
 42     head[u] = cnt++;
 43 }
 44 
 45 void tarjan(int u){
 46 
 47     
 48     DFN[u] = LOW[u] = ++dfn;
 49     sta.push(u);
 50     insta[u] = true;
 51 
 52     for(int o = head[u]; ~o; o = e[o].next){
 53         int v = e[o].to;
 54 
 55         if(!DFN[v]){
 56             tarjan(v);
 57             LOW[u] = min(LOW[u],LOW[v]);
 58         }
 59         else if(insta[v]){
 60             LOW[u] = min(LOW[u],DFN[v]);
 61         }
 62     }
 63 
 64     if(LOW[u] == DFN[u]){
 65         ++scccnt;
 66         scc[scccnt].clear();
 67         while(1){    
 68             int v = sta.top();
 69             sta.pop();
 70             sccno[v] = scccnt; //缩点
 71             insta[v] = false;
 72             scc[scccnt].push_back(v); //缩点
 73             
 74             if(v == u) break;
 75         }
 76 
 77         sccdeep[scccnt] = scc[scccnt].size(); //包含几个点
 78         // cout << scccnt << " num " << sccdeep[scccnt] << endl;
 79     }
 80 }
 81 
 82 void dfs(int ucnt){
 83 
 84     //xcnt  属于哪一块分量
 85 
 86     int u = scc[ucnt][0]; //该点
 87     visscc[ucnt] = true;
 88     for(int o = head[u]; ~o; o = e[o].next){
 89         int v = e[o].to; //去的点
 90         int vcnt = sccno[v]; 
 91         if(v == u) break;//自己成环
 92         if(visscc[vcnt]) sccdeep[ucnt] += sccdeep[vcnt];
 93         else{
 94             dfs(vcnt);
 95             sccdeep[ucnt] += sccdeep[vcnt];
 96         }
 97 
 98         /*这里给一组数据方便理解
 99             5
100             2
101             3
　　　　　　　　　 1
102             5
103             1
104         */    
105     }
106 }
107 
108 void print(){
109 
110     rep(i,1,n){
111         cout << sccdeep[sccno[i]] << endl;
112     }
113 }
114 
115 int main(){
116 
117     ios::sync_with_stdio(false);
118     cin.tie(0);
119 
120     cin >> n;
121 
122     rep(i,1,n) head[i] = -1; //头
123     cnt = 0; //边数
124     int v;
125     rep(u,1,n){
126         cin >> v;
127         add(u,v);
128     }
129 
130     // rep(i,1,n){
131     //     for(int o = head[i]; ~o; o = e[o].next)
132     //         cout << i << ' ' << e[o].to << endl;
133     // }
134 
135     rep(i,1,n) insta[i] = sccno[i] = DFN[i] = LOW[i] = sccdeep[i] = 0;
136     scccnt = dfn = 0;
137     rep(i,1,n) if(!DFN[i]){
138         tarjan(i);
139     }
140 
141 
142     rep(i,1,scccnt) if(sccdeep[i] >= 2) visscc[i] = true; //点数超过2个的分量是环，先处理了
143     rep(i,1,scccnt) if(!visscc[i]){
144         dfs(i);
145     }
146 
147     print();
148 
149     getchar(); getchar();
150     return 0;
151 }