6.12白书第五章图论总结—

6.12白书第五章图论总结——司雨寒

之前我的图论一直都是DFS一下，BFS一下，求个欧拉回路，拓扑排个序这种渣渣水平。

终于鼓起勇气拾起白书第五章的东西。

学(bei)习(song)了一下求双连通分量，二分图的判定，强连通分量，2-SAT。

DFS加上时间戳这个东西，很强大。

最后刷了白书上的例题：

BCC：

LA3523

可以参加会议的是双联通分量上的奇圈

  1 #include <cstdio>
  2 #include <cstring>
  3 #include <algorithm>
  4 #include <vector>
  5 #include <stack>
  6 using namespace std;
  7 
  8 struct Edge
  9 {
 10     int u, v;
 11     Edge(int u, int v):u(u), v(v) {}
 12 };
 13 
 14 const int maxn = 1000 + 10;
 15 int n, m;
 16 
 17 bool A[maxn][maxn];
 18 vector<int> G[maxn];
 19 
 20 void init()
 21 {
 22     for(int i = 0; i < n; i++) G[i].clear();
 23     memset(A, false, sizeof(A));
 24 }
 25 
 26 int pre[maxn], bccno[maxn], dfs_clock, bcc_cnt;
 27 bool iscut[maxn];
 28 vector<int> bcc[maxn];
 29 stack<Edge> S;
 30 
 31 int dfs(int u, int fa)
 32 {
 33     int lowu = pre[u] = ++dfs_clock;
 34     int child = 0;
 35     for(int i = 0; i < G[u].size(); i++)
 36     {
 37         int v = G[u][i];
 38         Edge e = Edge(u, v);
 39         if(!pre[v])
 40         {
 41             S.push(e);
 42             child++;
 43             int lowv = dfs(v, u);
 44             lowu = min(lowu, lowv);
 45             if(lowv >= pre[u])
 46             {
 47                 iscut[u] = true;
 48                 bcc_cnt++; bcc[bcc_cnt].clear();
 49                 for(;;)
 50                 {
 51                     Edge x = S.top(); S.pop();
 52                     if(bccno[x.u] != bcc_cnt) { bcc[bcc_cnt].push_back(x.u); bccno[x.u] = bcc_cnt; }
 53                     if(bccno[x.v] != bcc_cnt) { bcc[bcc_cnt].push_back(x.v); bccno[x.v] = bcc_cnt; }
 54                     if(x.u == u && x.v == v) break;
 55                 }
 56             }
 57         }
 58         else if(pre[v] < pre[u] && v != fa)
 59         {
 60             S.push(e);
 61             lowu = min(lowu, pre[v]);
 62         }
 63     }
 64 
 65     if(fa < 0 && child == 1) iscut[u] = false;
 66     return lowu;
 67 }
 68 
 69 void find_bcc()
 70 {
 71     memset(pre, 0, sizeof(pre));
 72     memset(iscut, false, sizeof(iscut));
 73     memset(bccno, 0, sizeof(bccno));
 74     dfs_clock = bcc_cnt = 0;
 75 
 76     for(int i = 0; i < n; i++)
 77         if(!pre[i]) dfs(i, -1);
 78 }
 79 
 80 int color[maxn];
 81 bool odd[maxn];
 82 
 83 bool bipartite(int u, int b)
 84 {
 85     for(int i = 0; i < G[u].size(); i++)
 86     {
 87         int v = G[u][i]; if(bccno[v] != b) continue;
 88         if(color[u] == color[v]) return false;
 89         else if(!color[v])
 90         {
 91             color[v] = 3 - color[u];
 92             if(!bipartite(v, b)) return false;
 93         }
 94     }
 95 
 96     return true;
 97 }
 98 
 99 int main()
100 {
101     while(scanf("%d%d", &n, &m) == 2 && n)
102     {
103         init();
104 
105         while(m--)
106         {
107             int u, v;
108             scanf("%d%d", &u, &v); u--; v--;
109             A[u][v] = A[v][u] = true;
110         }
111 
112         for(int u = 0; u < n; u++)
113             for(int v = u + 1; v < n; v++)
114                 if(!A[u][v]) { G[u].push_back(v); G[v].push_back(u); }
115 
116         find_bcc();
117 
118         memset(odd, false, sizeof(odd));
119         for(int i = 1; i <= bcc_cnt; i++)
120         {
121             memset(color, 0, sizeof(color));
122             for(int j = 0; j < bcc[i].size(); j++)
123                 bccno[bcc[i][j]] = i;
124             int u = bcc[i][0];
125             color[u] = 1;
126             if(!bipartite(u, i))
127                 for(int j = 0; j < bcc[i].size(); j++)
128                     odd[bcc[i][j]] = true;
129         }
130 
131         int ans = 0;
132         for(int i = 0; i < n; i++) if(!odd[i]) ans++;
133         printf("%d
", ans);
134     }
135 
136     return 0;
137 }

代码君

LA 5135

统计只有一个割顶的双联通分量非割顶的顶点的个数的乘积

  1 #include <cstdio>
  2 #include <cstring>
  3 #include <algorithm>
  4 #include <stack>
  5 #include <vector>
  6 #include <map>
  7 using namespace std;
  8 
  9 struct Edge
 10 {
 11     int u, v;
 12     Edge(int u, int v):u(u), v(v) {}
 13 };
 14 
 15 const int maxn = 100000 + 10;
 16 
 17 int n;
 18 
 19 int pre[maxn], bccno[maxn], dfs_clock, bcc_cnt;
 20 bool iscut[maxn];
 21 vector<int> G[maxn], bcc[maxn];
 22 stack<Edge> S;
 23 
 24 int dfs(int u, int fa)
 25 {
 26     int lowu = pre[u] = ++dfs_clock;
 27     int child = 0;
 28     for(int i = 0; i < G[u].size(); i++)
 29     {
 30         int v = G[u][i];
 31         Edge e = (Edge) { u, v };
 32         if(!pre[v])
 33         {
 34             S.push(e);
 35             child++;
 36             int lowv = dfs(v, u);
 37             lowu = min(lowv, lowu);
 38             if(lowv >= pre[u])
 39             {
 40                 iscut[u] = true;
 41                 bcc_cnt++; bcc[bcc_cnt].clear();
 42                 for(;;)
 43                 {
 44                     Edge x = S.top(); S.pop();
 45                     if(bccno[x.u] != bcc_cnt) { bcc[bcc_cnt].push_back(x.u); bccno[x.u] = bcc_cnt; }
 46                     if(bccno[x.v] != bcc_cnt) { bcc[bcc_cnt].push_back(x.v); bccno[x.v] = bcc_cnt; }
 47                     if(x.u == u && x.v == v) break;
 48                 }
 49             }
 50         }
 51         else if(pre[v] < pre[u] && v != fa)
 52         {
 53             S.push(e);
 54             lowu = min(lowu, pre[v]);
 55         }
 56     }
 57     if(fa < 0 && child == 1) iscut[u] = false;
 58     return lowu;
 59 }
 60 
 61 int tot;
 62 map<int, int> id;
 63 int ID(int x) { if(!id.count(x)) id[x] = tot++; return id[x]; }
 64 
 65 void init()
 66 {
 67     memset(pre, 0, sizeof(pre));
 68     memset(iscut, false, sizeof(iscut));
 69     memset(bccno, 0, sizeof(bccno));
 70     for(int i = 0; i < n*2; i++) G[i].clear();
 71     tot = dfs_clock = bcc_cnt = 0;
 72     id.clear();
 73 }
 74 
 75 int main()
 76 {
 77     int kase = 0;
 78     while(scanf("%d", &n) == 1 && n)
 79     {
 80         init();
 81 
 82         while(n--)
 83         {
 84             int u, v; scanf("%d%d", &u, &v);
 85             G[u].push_back(v);
 86             G[v].push_back(u);
 87         }
 88         dfs(1, -1);
 89 
 90         long long ans1 = 0, ans2 = 1;
 91         for(int i = 1; i <= bcc_cnt; i++)
 92         {
 93             int cut_cnt = 0;
 94             for(int j = 0; j < bcc[i].size(); j++)
 95                 if(iscut[bcc[i][j]]) cut_cnt++;
 96             if(cut_cnt == 1)
 97             {
 98                 ans1++;
 99                 ans2 *= (long long)(bcc[i].size() - 1);
100             }
101         }
102         if(bcc_cnt == 1) { ans1 = 2; ans2 = (long long)bcc[1].size() * (bcc[1].size() - 1) / 2; }
103 
104         printf("Case %d: %lld %lld
", ++kase, ans1, ans2);
105     }
106 
107     return 0;
108 }

代码君

SCC：

LA 4287

为了使原图整个强连通，添加的最少的边数为max{入读为0的顶点的个数，出度为0的顶点的个数}

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <stack>
 4 #include <vector>
 5 #include <algorithm>
 6 using namespace std;
 7 
 8 const int maxn = 20000 + 10;
 9 int n, m;
10 vector<int> G[maxn];
11 
12 int pre[maxn], lowlink[maxn], sccno[maxn], dfs_clock, scc_cnt;
13 stack<int> S;
14 
15 void dfs(int u)
16 {
17     pre[u] = lowlink[u] = ++dfs_clock;
18     S.push(u);
19     for(int i = 0; i < G[u].size(); i++)
20     {
21         int v = G[u][i];
22         if(!pre[v])
23         {
24             dfs(v);
25             lowlink[u] = min(lowlink[u], lowlink[v]);
26         }
27         else if(!sccno[v]) lowlink[u] = min(lowlink[u], pre[v]);
28     }
29 
30     if(lowlink[u] == pre[u])
31     {
32         scc_cnt++;
33         for(;;)
34         {
35             int x = S.top(); S.pop();
36             sccno[x] = scc_cnt;
37             if(x == u) break;
38         }
39     }
40 }
41 
42 void find_scc()
43 {
44     dfs_clock = scc_cnt = 0;
45     memset(pre, 0, sizeof(pre));
46     memset(sccno, 0, sizeof(sccno));
47     for(int i = 0; i < n; i++)
48         if(!pre[i]) dfs(i);
49 }
50 
51 int in0[maxn], out0[maxn];
52 
53 int main()
54 {
55     int T; scanf("%d", &T);
56     while(T--)
57     {
58         scanf("%d%d", &n, &m);
59         for(int i = 0; i < n; i++) G[i].clear();
60         while(m--)
61         {
62             int u, v; scanf("%d%d", &u, &v);
63             u--; v--;
64             G[u].push_back(v);
65         }
66 
67         find_scc();
68 
69         if(scc_cnt == 1) { puts("0"); continue; }
70 
71         for(int i = 1; i <= scc_cnt; i++) in0[i] = out0[i] = 1;
72 
73         for(int u = 0; u < n; u++)
74             for(int i = 0; i < G[u].size(); i++)
75             {
76                 int v = G[u][i];
77                 if(sccno[u] != sccno[v]) out0[sccno[u]] = in0[sccno[v]] = 0;
78             }
79 
80         int a = 0, b = 0;
81         for(int i = 1; i <= scc_cnt; i++)
82         {
83             if(in0[i]) a++;
84             if(out0[i]) b++;
85         }
86         printf("%d
", max(a, b));
87     }
88 
89     return 0;
90 }

代码君

UVa 11324

对于每个SCC中的点，要么全选要么全不选。

求SCC通常是为了缩点，求完SCC后可以转化为一个DAG，然后用记忆化搜索求权值和最大的路径。

  1 #include <cstdio>
  2 #include <cstring>
  3 #include <algorithm>
  4 #include <vector>
  5 #include <stack>
  6 using namespace std;
  7 
  8 const int maxn = 1000 + 10;
  9 int n, m;
 10 
 11 vector<int> G[maxn];
 12 
 13 void init()
 14 {
 15     for(int i = 1; i <= n; i++) G[i].clear();
 16 }
 17 
 18 int pre[maxn], lowlink[maxn], sccno[maxn], dfs_clock, scc_cnt;
 19 stack<int> S;
 20 
 21 void dfs(int u)
 22 {
 23     pre[u] = lowlink[u] = ++dfs_clock;
 24     S.push(u);
 25     for(int i = 0; i < G[u].size(); i++)
 26     {
 27         int v = G[u][i];
 28         if(!pre[v])
 29         {
 30             dfs(v);
 31             lowlink[u] = min(lowlink[u], lowlink[v]);
 32         }
 33         else if(!sccno[v]) lowlink[u] = min(lowlink[u], pre[v]);
 34     }
 35     if(lowlink[u] == pre[u])
 36     {
 37         scc_cnt++;
 38         for(;;)
 39         {
 40             int x = S.top(); S.pop();
 41             sccno[x] = scc_cnt;
 42             if(x == u) break;
 43         }
 44     }
 45 }
 46 
 47 void find_bcc()
 48 {
 49     dfs_clock = scc_cnt = 0;
 50     memset(sccno, 0, sizeof(sccno));
 51     memset(pre, 0, sizeof(pre));
 52     for(int i = 1; i <= n; i++)
 53         if(!pre[i]) dfs(i);
 54 }
 55 
 56 bool G2[maxn][maxn];
 57 int w[maxn];
 58 
 59 int d[maxn];
 60 
 61 int dp(int u)
 62 {
 63     if(d[u] >= 0) return d[u];
 64     int& ans = d[u];
 65     ans = w[u];
 66     for(int v = 1; v <= scc_cnt; v++) if(G2[u][v])
 67         ans = max(ans, dp(v) + w[u]);
 68     return ans;
 69 }
 70 
 71 int main()
 72 {
 73     int T; scanf("%d", &T);
 74     while(T--)
 75     {
 76         scanf("%d%d", &n, &m);
 77         init();
 78         while(m--)
 79         {
 80             int u, v; scanf("%d%d", &u, &v);
 81             G[u].push_back(v);
 82         }
 83 
 84         find_bcc();
 85 
 86         memset(G2, false, sizeof(G2));
 87         memset(w, 0, sizeof(w));
 88         for(int i = 1; i <= n; i++)
 89         {
 90             int u = sccno[i];
 91             w[u]++;
 92             for(int j = 0; j < G[i].size(); j++)
 93             {
 94                 int v = sccno[G[i][j]];
 95                 if(u != v) G2[u][v] = true;
 96             }
 97         }
 98 
 99         memset(d, -1, sizeof(d));
100         int ans = 0;
101         for(int i = 1; i <= scc_cnt; i++)
102             ans = max(ans, dp(i));
103         printf("%d
", ans);
104     }
105 
106     return 0;
107 }

代码君

2-SAT

LA 3211

二分最小时间间隔T，枚举任意两个飞机早晚的起飞时间，如果时间间隔小于T的话则加一个句子，所以最多不超过n(n-1)/2个句子。

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <algorithm>
 4 #include <vector>
 5 #include <cmath>
 6 using namespace std;
 7 
 8 const int maxn = 2000 + 10;
 9 int T[maxn][2];
10 
11 int n;
12 
13 vector<int> G[maxn * 2];
14 bool mark[maxn * 2];
15 int S[maxn * 2], top;
16 
17 void init()
18 {
19     for(int i = 0; i < n * 2; i++) G[i].clear();
20     memset(mark, false, sizeof(mark));
21 }
22 
23 void add_clause(int x, int xvalue, int y, int yvalue)
24 {
25     x = x * 2 + xvalue;
26     y = y * 2 + yvalue;
27     G[x^1].push_back(y);
28     G[y^1].push_back(x);
29 }
30 
31 bool dfs(int u)
32 {
33     if(mark[u^1]) return false;
34     if(mark[u]) return true;
35     mark[u] = true;
36     S[++top] = u;
37     for(int i = 0; i < G[u].size(); i++)
38     {
39         int v = G[u][i];
40         if(!dfs(v)) return false;
41     }
42     return true;
43 }
44 
45 bool solve()
46 {
47     for(int i = 0; i < n*2; i += 2)
48     {
49         if(!mark[i] && !mark[i+1])
50         {
51             top = -1;
52             if(!dfs(i))
53             {
54                 while(top >= 0) mark[S[top--]] = false;
55                 if(!dfs(i + 1)) return false;
56             }
57         }
58     }
59     return true;
60 }
61 
62 bool ok(int t)
63 {
64     init();
65     for(int i = 0; i < n; i++) for(int a = 0; a < 2; a++)
66         for(int j = i + 1; j < n; j++) for(int b = 0; b < 2; b++)
67             if(abs(T[i][a] - T[j][b]) < t) add_clause(i, a^1, j, b^1);
68     return solve();
69 }
70 
71 int main()
72 {
73     //freopen("in.txt", "r", stdin);
74 
75     while(scanf("%d", &n) == 1)
76     {
77         int L = 0, R = 0;
78         for(int i = 0; i < n; i++)
79         {
80             scanf("%d%d", &T[i][0], &T[i][1]);
81             R = max(R, T[i][0]);
82             R = max(R, T[i][1]);
83         }
84 
85         while(L < R)
86         {
87             int mid = (L + R) / 2 + 1;
88             if(ok(mid)) L = mid;
89             else R = mid - 1;
90         }
91         printf("%d
", L);
92     }
93 
94     return 0;
95 }

代码君