[USACO5.3]校园网Network of Schools

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

缩点

蒟蒻在这道题上wa了六次……

错误一：

结论推错了

任务B的答案是根数和叶子数中较小的那个

也就是说加路前的各个树加路之后不一定是强连通分量

错误二：

特判当只有一个点的时候任务二输出0

 1 int main(){
 2     init();
 3     for(int i = 1; i <= n; i++)
 4        if(!dfn[i]) tarjan(i);
 5     for(int i = 1; i <= esize[0]; i++){
 6         int vv = edge[0][i].v, uu = edge[0][i].u;
 7         if(col[uu] != col[vv]){
 8             addedge(col[uu], col[vv], 1);
 9             ind[col[vv]]++;
10             out[col[uu]]++;
11         }
12     }
13     int ans1 = 0, ans2 = 0;
14     for(int i = 1; i <= csize; i++){
15         if(!ind[i]) ans1++;
16         if(!out[i]) ans2++;
17     }
18     printf("%d
", ans1);
19     if(csize == 1) printf("0
");
20     else printf("%d
", max(ans1, ans2));
21     return 0;
22 }

主体框架

 1 void tarjan(int x){
 2 //    printf("%d
", x);
 3     low[x] = dfn[x] = ++dc;
 4     s.push(x); ins[x] = 1;
 5     for(int i = head[0][x]; i != -1; i = edge[0][i].next){
 6         int vv = edge[0][i].v;
 7         if(!dfn[vv]){
 8             tarjan(vv);
 9             low[x] = min(low[x], low[vv]);
10         }
11         else if(ins[vv]) low[x] = min(low[x], low[vv]);
12     }
13     if(dfn[x] == low[x]){
14         ++csize;
15         int top;
16         do{
17             top = s.top(); s.pop();
18             col[top] = csize;
19             ins[top] = 0;
20         }
21         while(top != x);
22     }
23 }

tarjan缩点