Luogu 2812 校园网络 - Tarjan

Description

给出一个有向图， 要求出至少从哪几个点出发， 能不漏地经过所有节点。

再求出至少加几条边， 才能使图变成一个强联通分量

Solution

求出所有强联通分量， 形成一个有向无环图， 第一问题就是求出有多少强联通分量的入度为 $0$

第二个问题就是求出 入度为$0 $和 出度为$0$  的强联通分量的数量  的 最大值， 想象一下就可以了。

在整个图都是强联通分量下， 第二个问题答案为 $0$。

Code

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 #define rd read()

 #define rep(i,a,b) for(int i = (a); i <= (b); ++i)

 #define per(i,a,b) for(int i = (a); i >= (b); --i)

 using namespace std;

 const int N = ;

 const int M = 6e6;

 int head[N], tot;

 int col[N], col_num, size[N];

 int n, dfn[N], low[N], cnt, vis[N];

 int st[N], tp, ans1, ans2;

 int chu[N], ru[N];

 struct edge {

     int nxt, to, fr;

 }e[M];

 int read() {

     int X = , p = ; char c = getchar();

     for(; c > '' || c < ''; c = getchar()) if(c == '-') p = -;

     for(; c >= '' && c <= ''; c = getchar()) X = X *  + c - '';

     return X * p;

 }

 void add(int u, int v) {

     e[++tot].to = v;

     e[tot].nxt = head[u];

     e[tot].fr = u;

     head[u] = tot;

 }

 void tarjan(int u) {

     dfn[u] = low[u] = ++cnt;

     st[++tp] = u;

     vis[u] = ;

     for(int i = head[u]; i; i = e[i].nxt) {

         int nt = e[i].to;

         if(!dfn[nt]) tarjan(nt), low[u] = min(low[u], low[nt]);

         else if(vis[nt]) low[u] = min(low[u], dfn[nt]);

     }

     if(dfn[u] == low[u]) {

         col_num++;

         for(; tp;) {

             int nt = st[tp--];

             vis[nt] = ;

             col[nt] = col_num;

             if(nt == u) break;

         }

     }

 }

 int main()

 {

     n = rd;

     for(int i = ; i <= n; ++i) {

         for(; ;) {

             int x = rd;

             if(!x) break;

             add(i, x);

         }

     }

     for(int i = ; i <= n; ++i)

         if(!dfn[i]) tarjan(i);

     for(int i = ; i <= tot; ++i) {

         int x = e[i].fr, y = e[i].to;

         if(col[x] == col[y]) continue;

         ru[col[y]]++; chu[col[x]]++;

     }

     for(int i = ; i <= col_num; ++i)

         if(!ru[i]) ans1++;

     printf("%d\n", ans1);

     if(col_num == ) return printf("0\n"), ;

     for(int i = ; i <= col_num; ++i)

         if(!chu[i]) ans2++;

     printf("%d\n", max(ans1, ans2));

 }