定向时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 262144K，其他语言524288KSpecial Judge, 64bit IO Format: %lld题目描述给一张无向图，你需要将边定向，使得定向后的有向图强连通。输入描述:第一行两个数n,m，表示点数和边数。接下来m行，每个两个数x,y，表示x和y之间有条边。输出描述:如果不存在可行方案输出一行"impossible" ；否则，输出一个长度为m的01串，描述你的方案，第i个字符为1表示输入的第i条边定向为从x到y，为0表示从y到x。输入3 3 1 2 1 3 2 3输出101说明1->2->3->1，形成一个环 ，是强连通的。备注$1 ≤ n,m ≤ 10^6$ ，保证无重边自环链接https://www.nowcoder.com/acm/contest/158/E题意如题，确定无向图边的反向，使得其形成的有向图强连通，无解输出impossible。题解dfs出一棵生成树，令所有树边从父亲指向儿子，所有返祖边从后代指向祖先。判断这样构造的有向图是否强连通即可。 正确性证明如下: 如果无向图不连通或者存在割边显然无解，否则这样构造一定是一组解。 因为考虑求割边的过程，不存在割边就意味着每个点都能走回他的祖先， 所以在这样构造的有向图里，每个点也依旧能走回他的祖先。使用Tarjan判断是否存在桥，有桥那么无解，否则dfs一遍得到边的方向。代码运行结果运行时间(ms)使用内存(KB)代码长度使用语言答案正确1120402871C++#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <queue> #include <vector> #include <stack> using namespace std; const int maxn = 100010; const int maxm = 100010; struct Edge { int to, next; bool cut; // 是否为桥 bool used; // 是否遍历过 int dir; // 方向 }edge[maxm<<2]; int head[maxn], tot, n, m; int low[maxn], dfn[maxn], Stack[maxn], add_block[maxn]; // 删除一个点后增加的连通块 int Index, top; bool Instack[maxn], cut[maxn], vis[maxn]; int bridge; void init() { memset(head, -1, sizeof(head)); tot = 0; } void addedge(int u, int v) { edge[tot].to = v; edge[tot].next = head[u]; edge[tot].cut = false; edge[tot].used = false; head[u] = tot++; } void Tarjan(int u, int pre) // 求解无向图割点和桥 { int v; low[u] = dfn[u] = ++Index; Stack[top++] = u; Instack[u] = true; int son = 0; bool flag = true; for (int i = head[u]; i != -1; i = edge[i].next) { v = edge[i].to; if (v == pre && flag) // 重边 { flag = false; continue; } if (!dfn[v]) { son++; Tarjan(v, u); low[u] = min(low[u], low[v]); if (low[v] > dfn[u]) // 桥 { bridge++; edge[i].cut = true; edge[i^1].cut = true; } if (u != pre && low[v] >= dfn[u]) // 割点，非树根 { cut[u] = true; add_block[u]++; } } else if (low[u] > dfn[v]) low[u] = dfn[v]; } if (u == pre && son > 1) // 树根，分支数大于1 cut[u] = true; if (u == pre) add_block[u] = son - 1; Instack[u] = false; top--; } void dfs(int u) { for (int i = head[u]; i != -1; i = edge[i].next) { int v = edge[i].to; if (edge[i].used) // 边已访问 continue; edge[i].used = true, edge[i^1].used = true; edge[i].dir = 0, edge[i^1].dir = 1; // 确定关系 dfs(v); } } void solve() { memset(dfn, 0, sizeof(dfn)); memset(Instack, 0, sizeof(Instack)); memset(add_block, 0, sizeof(add_block)); memset(cut, 0, sizeof(cut)); memset(vis, 0, sizeof(vis)); Index = top = 0; bridge = 0; int cnt = 0; for (int i = 1; i <= n; ++i) { if (!dfn[i]) { Tarjan(i, i); cnt++; } } if (cnt > 1 || bridge > 0) printf("impossible\n"); else { dfs(1); for (int i = 0; i < tot; i += 2) printf("%d", edge[i].dir); printf("\n"); } } int main() { int u, v; while (scanf("%d%d", &n, &m) != EOF) { init(); for (int i = 0; i < m; ++i) { scanf("%d%d", &u, &v); addedge(u, v); addedge(v, u); } solve(); } return 0; }The end.2018-08-27 星期一
RailwayTime Limit: 2000/1000 MS (Java/Others)Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 3467Accepted Submission(s): 1159Problem DescriptionThere are some locations in a park, and some of them are connected by roads. The park manger needs to build some railways along the roads, and he would like to arrange tourist routes to each circuit. If a railway belongs to more than one tourist routes, there might be clash on it, and if a railway belongs to none tourist route, it doesn’t need to build.Now we know the plan, and can you tell us how many railways are no need to build and how many railways where clash might happen.InputThe Input consists of multiple test cases. The first line of each test case contains two integers, n (0 < n <= 10000), m (0 <= m <= 100000), which are the number of locations and the number of the railways. The next m lines, each line contains two integers, u, v (0 <= u, v < n), which means the manger plans to build a railway on the road between u and v.You can assume that there is no loop and no multiple edges.The last test case is followed by two zeros on a single line, which means the end of the input.OutputOutput the number of railways that are no need to build, and the number of railways where clash might happen. Please follow the format as the sample.Sample Input8 10 0 1 1 2 2 3 3 0 3 4 4 5 5 6 6 7 7 4 5 7 0 0Sample Output1 5SourceThe 5th Guangting Cup Central China Invitational Programming Contest链接http://acm.hdu.edu.cn/showproblem.php?pid=3394题意给一个无向图。如果至少有两个环共用了一些边，那么这些边被认为是“冲突边”。如果一些边不在任何一个环中，这些边被认为是“多余边”。分别输出图中“多余边”和“冲突边”的数量。题解“多余边”不在任何一个环中，那么多余边一定是桥，所以统计这个无向图中有多少桥即可。“冲突边”有多少，这个有点费劲，但是不难想到。如果一个环比较特殊，n个点刚好n条边，例如(1, 2)、(1, 3)、(2, 3)这种环，这个环内，一条“冲突边”都没有，但是如果一个环内的边数大于点数，那么这个环内所有边都是“冲突边”（真可惜，因为有多出来的那些边后，相当于把最外面的大环分割成了内部的几个小环，这些小环和小环之间，小环和大环之间一定会公用一些边，这些边就是“冲突边”，而且可以发现，所有边都会被公用，太可惜了......），例如sample里面的(5,6)(5,4)(6,7)(4,7)(5,7)，相当于最外面的大环<6,5,4,7,6> ， 而里面的边(5,7)把这个大环分割成了两个小环。因为是求环,所以求的是点双连通分量。所以做法就是，求出这个无向图有多少个点双连通分量，对于每个点双连通分量，如果内部的边数>点数，那么这些边全部都是冲突边。参考了Gitfan的题解。代码StatusAcceptedTime358msMemory8608kBLength3164#include <iostream> #include <algorithm> #include <cstdio> #include <cstring> #include <stack> #include <vector> using namespace std; const int maxn = 10010; const int maxm = 200010; int n, m, tot, cnt, bcc_cnt, bridges; // 连通分量数量和桥数量 int head[maxn], dfn[maxn], low[maxn], bccno[maxn], iscut[maxn]; // 连通分量编号和割点标记 struct Node { int to, next, cut; }edge[maxm]; void addedge(int u, int v) // 链式前向星存图 { edge[cnt].cut = 0; edge[cnt].to = v; edge[cnt].next = head[u]; head[u] = cnt++; } struct Edge // 边 { int u, v; Edge(){} Edge(int u, int v):u(u), v(v){} }; stack <Edge> S; // 栈中保存连通分量的边 vector<int>bcc[maxn]; // 连通分量中的点 vector<Edge>edgecnt[maxn]; // 连通分量重的边数 void init() // 初始化 { bcc_cnt = tot = cnt = bridges = 0; for (int i = 0; i <= n; ++i) { head[i] = -1; dfn[i] = low[i] = bccno[i] = iscut[i] = 0; bcc[i].clear(); edgecnt[i].clear(); } memset(edge, 0, sizeof(edge)); } void tarjan(int u, int father) // tarjan求连通分量 { low[u] = dfn[u] = ++tot; int child = 0; bool flag = true; for (int i = head[u]; i != -1; i = edge[i].next) { int v = edge[i].to; if (flag && v == father) // 处理可能存在的重边 { flag = false; continue; } Edge e(u, v); if (!dfn[v]) { S.push(e); child++; tarjan(v, u); low[u] = min(low[u], low[v]); if (low[v] >= dfn[u]) // 割顶 { iscut[u] = true; bcc_cnt++; while (1) // 取出栈中连通分量 { Edge tmp = S.top(); S.pop(); edgecnt[bcc_cnt].push_back(tmp); // 防止重复加点 if (bccno[tmp.u] != bcc_cnt) { bcc[bcc_cnt].push_back(tmp.u); bccno[tmp.u] = bcc_cnt; } if (bccno[tmp.v] != bcc_cnt) { bcc[bcc_cnt].push_back(tmp.v); bccno[tmp.v] = bcc_cnt; } if (tmp.u == u && tmp.v == v) break; } } if (low[v] > dfn[u]) // 桥 { edge[i].cut = 1; edge[i+1].cut = 1; bridges++; } } else if (dfn[v] < dfn[u]) // 用反向边进行更新 { S.push(e); low[u] = min(low[u], dfn[v]); } } if (father < 0 && child == 1) iscut[u] = 0; } void solve() { for (int i = 1; i <= n; ++i) // 图可能不连通 { if (!dfn[i]) tarjan(i, -1); } int edges = 0; for (int i = 1; i <= bcc_cnt; ++i) { if (edgecnt[i].size() > bcc[i].size()) // 判断连通分量中的点数与边数 edges += edgecnt[i].size(); } printf("%d %d\n", bridges, edges); } int main() { while (scanf("%d%d", &n, &m) == 2) { if (n == 0 && m == 0) break; init(); int u, v; for (int i = 0; i < m; ++i) { scanf("%d%d", &u, &v); u++, v++; addedge(u, v); addedge(v, u); } solve(); } return 0; }对求无向图的点双连通分量还是不太熟悉，不过图的连通性问题算是到此结束了。The end.2018-07-18 星期三
POJ3177 Redundant Paths（Tarjan求有重边双连通分量缩点）
Redundant PathsTime Limit: 1000MSMemory Limit: 65536KTotal Submissions: 18207Accepted: 7554DescriptionIn order to get from one of the F (1 <= F <= 5,000) grazing fields (which are numbered 1..F) to another field, Bessie and the rest of the herd are forced to cross near the Tree of Rotten Apples. The cows are now tired of often being forced to take a particular path and want to build some new paths so that they will always have a choice of at least two separate routes between any pair of fields. They currently have at least one route between each pair of fields and want to have at least two. Of course, they can only travel on Official Paths when they move from one field to another. Given a description of the current set of R (F-1 <= R <= 10,000) paths that each connect exactly two different fields, determine the minimum number of new paths (each of which connects exactly two fields) that must be built so that there are at least two separate routes between any pair of fields. Routes are considered separate if they use none of the same paths, even if they visit the same intermediate field along the way. There might already be more than one paths between the same pair of fields, and you may also build a new path that connects the same fields as some other path.InputLine 1: Two space-separated integers: F and R Lines 2..R+1: Each line contains two space-separated integers which are the fields at the endpoints of some path.OutputLine 1: A single integer that is the number of new paths that must be built.Sample Input7 7 1 2 2 3 3 4 2 5 4 5 5 6 5 7Sample Output2HintExplanation of the sample: One visualization of the paths is: 1 2 3 +---+---+ | | | | 6 +---+---+ 4 / 5 / / 7 + Building new paths from 1 to 6 and from 4 to 7 satisfies the conditions. 1 2 3 +---+---+ : | | : | | 6 +---+---+ 4 / 5 : / : / : 7 + - - - - Check some of the routes: 1 – 2: 1 –> 2 and 1 –> 6 –> 5 –> 2 1 – 4: 1 –> 2 –> 3 –> 4 and 1 –> 6 –> 5 –> 4 3 – 7: 3 –> 4 –> 7 and 3 –> 2 –> 5 –> 7 Every pair of fields is, in fact, connected by two routes. It's possible that adding some other path will also solve the problem (like one from 6 to 7). Adding two paths, however, is the minimum.SourceUSACO 2006 January Gold链接http://poj.org/problem?id=3177题意与POJ3352 Road Construction（Tarjan 求双连通分量缩点）一样，n 个节点 m 条边的无向图，问至少需要添加多少条边使这个图变成边双连通的。但是本题的数据有重边！！！所以需要特别处理一下。题解使用 Tarjan 求双连通分量，然后将同一个双连通分量缩点构成成一棵树，统计树上度为 1 的节点的数量 cnt，需要添加边的数量就是 (cnt+1)/2。两个点之间如果存在有重边，也算是双连通的。需要一个标记flag， 假如这个点到父亲的路有两条，那么第一条可以不走，但是第二条必须要走，因为是重边，这样儿子节点也就可以更新 low 了。代码StatusAcceptedMemory312kBLength4287#include <iostream> #include <algorithm> #include <cstdio> #include <cstring> #include <stack> using namespace std; const int maxn = 5010; int n, m, tot, cnt, cccnt; int dfn[maxn], low[maxn], head[maxn], ccno[maxn], ccnum[maxn], degree[maxn]; bool vis[maxn]; struct Edge { int to, next; }edge[20010]; stack <int> S; void addedge(int u, int v) { edge[cnt].to = v; edge[cnt].next = head[u]; head[u] = cnt++; } void init() { for (int i = 0; i <= n; ++i) { dfn[i] = low[i] = ccno[i] = ccnum[i] = degree[i] = 0; head[i] = -1; vis[i] = false; } memset(edge, 0, sizeof(edge)); tot = cccnt = 0; cnt = 1; } void tarjan(int u, int father) // 求双连通分量 { low[u] = dfn[u] = ++tot; S.push(u); vis[u] = true; bool flag = true; for (int i = head[u]; i != -1; i = edge[i].next) { int v = edge[i].to; if (v == father && flag) // 重边处理，与求桥类似 { flag = false; continue; } if (!dfn[v]) { tarjan(v, u); low[u] = min(low[u], low[v]); } else if (vis[v]) low[u] = min(low[u], dfn[v]); } if (low[u] == dfn[u]) // 栈中保存的是同一个连通分量 { cccnt++; while (1) { int v = S.top(); S.pop(); // printf("%d %d\n", cccnt, v); vis[v] = false; ccno[v] = cccnt; ccnum[cccnt]++; if (v == u) break; } } } int main() { scanf("%d%d", &n, &m); init(); int u, v; for (int i = 0; i < m; ++i) { scanf("%d%d", &u, &v); addedge(u, v); addedge(v, u); } tarjan(1, 0); for (int i = 1; i <= n; ++i) // 缩点成树求节点的度 { for (int j = head[i]; j != -1; j = edge[j].next) { int v = edge[j].to; if (ccno[i] != ccno[v]) degree[ccno[i]]++; } } int ans = 0; for (int i = 1; i <= cccnt; ++i) { if (degree[i] == 1) // 找到度为1的节点 ans++; } printf("%d\n", (ans+1) / 2); // 至少需要添加的边数 return 0; }推荐pku 3177 (3352) Redundant PathsPOJ 3177 Redundant Paths（重边标记法，有重边的边双连通分支）poj 3177 Redundant Paths(边双连通分量+缩点)数据来源于：传送门。Input for test 1 7 7 1 2 2 3 3 4 2 5 4 5 5 6 5 7 Output for test 1 2 Input for test 2 7 7 1 2 2 3 3 4 2 5 4 5 3 6 5 7 Output for test 2 2 Input for test 3 6 5 3 1 3 2 3 4 3 5 3 6 Output for test 3 3 Input for test 4 10 12 1 2 2 3 3 1 3 4 4 8 4 5 5 6 6 7 7 5 8 9 9 10 10 8 Output for test 4 2 Input for test 5 10 10 1 8 6 3 7 1 3 5 5 2 2 9 9 7 8 4 4 10 10 6 Output for test 5 0 Input for test 6 10 9 1 2 7 4 9 6 10 6 8 4 3 5 3 4 3 6 1 3 Output for test 6 3 Input for test 7 16 22 1 3 7 1 5 1 12 7 6 3 4 7 8 3 10 7 14 6 11 5 9 7 15 4 2 6 13 12 8 2 2 11 6 1 4 11 1 14 3 10 13 16 13 16 Output for test 7 2 Input for test 8 27 35 1 3 10 3 22 3 15 3 11 15 5 15 12 22 18 10 23 11 7 1 2 15 25 1 14 10 24 11 8 2 19 22 4 12 16 4 13 18 9 14 21 13 6 4 17 23 20 17 17 6 3 21 20 3 9 13 17 12 20 18 2 26 26 27 27 8 2 27 26 8 Output for test 8 4 Input for test 9 75 81 1 3 58 3 37 1 36 58 15 36 9 58 10 37 8 1 44 10 33 44 61 8 54 9 4 3 20 44 53 37 26 20 67 54 71 20 5 3 70 54 45 67 14 54 74 67 41 53 52 37 63 53 31 20 55 63 60 55 40 5 75 58 62 31 68 52 72 36 49 9 66 31 43 41 22 52 35 8 21 45 30 15 11 61 7 68 57 30 12 40 27 71 25 40 46 66 42 61 24 37 29 4 59 11 16 74 47 5 69 74 64 59 56 75 19 9 48 56 23 9 13 72 2 43 32 1 73 13 28 7 6 45 18 4 38 42 50 72 17 53 39 50 51 63 34 25 65 64 67 41 58 5 5 27 75 63 7 50 20 18 38 65 Output for test 9 16 Input for test 10 200 250 1 3 106 1 134 1 157 134 23 106 60 134 44 60 117 1 126 1 11 134 139 44 178 3 97 60 101 157 118 44 30 23 128 30 174 3 108 23 110 128 132 157 92 106 173 132 79 106 82 178 7 44 52 79 74 30 4 23 49 7 164 139 127 30 156 4 65 7 120 101 46 97 112 178 8 46 59 60 198 174 100 134 90 92 192 60 125 100 26 178 19 192 63 125 155 126 70 100 35 63 151 126 165 157 146 70 84 157 141 52 160 70 163 8 38 127 171 139 62 101 133 11 177 146 158 125 41 165 145 52 98 30 5 177 68 164 168 173 107 178 86 132 199 127 136 168 71 155 50 128 189 35 193 46 105 70 195 189 89 158 69 177 190 50 28 19 21 92 93 71 170 86 122 21 131 136 197 158 16 108 33 195 18 164 196 141 94 92 61 79 149 26 169 193 124 163 78 189 147 108 150 49 129 70 77 168 194 18 54 100 140 127 24 196 109 158 2 97 17 195 64 28 115 174 185 41 81 141 45 62 180 18 167 109 27 65 123 140 188 77 91 129 73 110 76 173 14 149 103 105 51 11 57 84 58 101 148 193 43 156 162 109 22 61 179 52 67 74 200 117 6 167 119 192 113 41 184 16 32 98 39 160 75 32 175 98 121 78 183 26 47 174 102 79 83 23 172 127 176 74 138 121 182 90 29 156 153 183 114 162 152 47 15 136 12 64 143 155 161 89 99 90 87 114 25 193 144 86 137 64 135 52 56 14 55 112 20 71 142 5 34 126 116 56 40 79 130 89 187 49 85 62 111 136 191 39 166 16 159 120 13 50 95 55 154 33 96 171 181 115 88 21 80 24 48 14 72 21 31 67 9 31 66 143 37 117 104 56 36 86 42 125 186 33 10 184 53 18 164 64 136 63 77 25 128 105 133 147 130 1 67 161 10 132 190 173 195 80 123 1 70 82 126 38 163 7 193 17 152 105 44 24 168 185 174 163 177 40 79 173 70 19 26 60 198 130 97 22 143 67 97 25 119 89 194 163 188 180 49 173 109 71 4 124 58 79 151 178 74 93 34 96 161 65 167 16 172 114 183 14 46 116 199 187 118 175 109 23 101 115 160 114 110 173 96 28 77 182 27 116 Output for test 10 32 Input for test 11 14 16 1 2 1 12 12 2 3 2 4 3 4 5 4 6 6 14 7 14 7 6 7 8 7 9 10 9 11 10 11 13 13 10 Output for test 11 2模板最后附上邝斌大大的板子。#include <stdio.h> #include <string.h> #include <iostream> #include <algorithm> #include using namespace std; const int MAXN = 5010;//点数 const int MAXM = 20010;//边数，因为是无向图，所以这个值要*2 struct Edge { int to,next; bool cut;//是否是桥标记 }edge[MAXM]; int head[MAXN],tot; int Low[MAXN],DFN[MAXN],Stack[MAXN],Belong[MAXN];//Belong数组的值是1~block int Index,top; int block;//边双连通块数 bool Instack[MAXN]; int bridge;//桥的数目 void addedge(int u,int v) { edge[tot].to = v;edge[tot].next = head[u];edge[tot].cut=false; head[u] = tot++; } void Tarjan(int u,int pre) { int v; Low[u] = DFN[u] = ++Index; Stack[top++] = u; Instack[u] = true; for(int i = head[u];i != -1;i = edge[i].next) { v = edge[i].to; if(v == pre)continue; if( !DFN[v] ) { Tarjan(v,u); if( Low[u] > Low[v] )Low[u] = Low[v]; if(Low[v] > DFN[u]) { bridge++; edge[i].cut = true; edge[i^1].cut = true; } } else if( Instack[v] && Low[u] > DFN[v] ) Low[u] = DFN[v]; } if(Low[u] == DFN[u]) { block++; do { v = Stack[--top]; Instack[v] = false; Belong[v] = block; } while( v!=u ); } } void init() { tot = 0; memset(head,-1,sizeof(head)); } int du[MAXN];//缩点后形成树，每个点的度数 void solve(int n) { memset(DFN,0,sizeof(DFN)); memset(Instack,false,sizeof(Instack)); Index = top = block = 0; Tarjan(1,0); int ans = 0; memset(du,0,sizeof(du)); for(int i = 1;i <= n;i++) for(int j = head[i];j != -1;j = edge[j].next) if(edge[j].cut) du[Belong[i]]++; for(int i = 1;i <= block;i++) if(du[i]==1) ans++; //找叶子结点的个数ans,构造边双连通图需要加边(ans+1)/2 printf("%d\n",(ans+1)/2); } int main() { int n,m; int u,v; while(scanf("%d%d",&n,&m)==2) { init(); while(m--) { scanf("%d%d",&u,&v); addedge(u,v); addedge(v,u); } solve(n); } return 0; }The end.2018-07-18 星期三
POJ3352 Road Construction（Tarjan求双连通分量缩点）
Road ConstructionTime Limit: 2000MSMemory Limit: 65536KTotal Submissions: 13401Accepted: 6758DescriptionIt's almost summer time, and that means that it's almost summer construction time! This year, the good people who are in charge of the roads on the tropical island paradise of Remote Island would like to repair and upgrade the various roads that lead between the various tourist attractions on the island.The roads themselves are also rather interesting. Due to the strange customs of the island, the roads are arranged so that they never meet at intersections, but rather pass over or under each other using bridges and tunnels. In this way, each road runs between two specific tourist attractions, so that the tourists do not become irreparably lost.Unfortunately, given the nature of the repairs and upgrades needed on each road, when the construction company works on a particular road, it is unusable in either direction. This could cause a problem if it becomes impossible to travel between two tourist attractions, even if the construction company works on only one road at any particular time.So, the Road Department of Remote Island has decided to call upon your consulting services to help remedy this problem. It has been decided that new roads will have to be built between the various attractions in such a way that in the final configuration, if any one road is undergoing construction, it would still be possible to travel between any two tourist attractions using the remaining roads. Your task is to find the minimum number of new roads necessary.InputThe first line of input will consist of positive integers n and r, separated by a space, where 3 ≤ n ≤ 1000 is the number of tourist attractions on the island, and 2 ≤ r ≤ 1000 is the number of roads. The tourist attractions are conveniently labelled from 1 to n. Each of the following r lines will consist of two integers, v and w, separated by a space, indicating that a road exists between the attractions labelled v and w. Note that you may travel in either direction down each road, and any pair of tourist attractions will have at most one road directly between them. Also, you are assured that in the current configuration, it is possible to travel between any two tourist attractions.OutputOne line, consisting of an integer, which gives the minimum number of roads that we need to add.Sample InputSample Input 1 10 12 1 2 1 3 1 4 2 5 2 6 5 6 3 7 3 8 7 8 4 9 4 10 9 10 Sample Input 2 3 3 1 2 2 3 1 3Sample OutputOutput for Sample Input 1 2 Output for Sample Input 2 0SourceCCC 2007链接http://poj.org/problem?id=3352题意n个节点m条边的无向图，问至少需要添加多少条边使这个图变成边双连通的。题解使用Tarjan求双连通分量，然后将同一个双连通分量缩点构成成一棵树，统计树上度为1的节点的数量cnt，需要添加边的数量就是(cnt+1)/2。貌似这题的数据是没有重边的。具体可参考BYVoid大佬的题解：题目大意是，给定一个连通图，要求添加一些边，使每两个顶点之间都有至少两条不相交的路径，求最小需要添加的边数。很显然，题中要求的图就是一个边双连通图，即边连通度不小于2。我的方法是在原图中DFS求出所有的桥，然后删除这些桥边，剩下的每个连通块都是一个双连通子图。把每个双连通子图收缩为一个顶点，再把桥边加回来，最后的这个图一定是一棵树，边连通度为1。统计出树中度为1的节点的个数，即为叶节点的个数，记为leaf。有人说至少在树上添加(leaf+1)/2条边，就能使树达到边二连通，所以结果就是(leaf+1)/2。这个结论我不能证明，但是可以想象出是对的。简单说明一下，首先把两个最近公共祖先最远的两个叶节点之间连接一条边，这样可以把这两个点到祖先的路径上所有点收缩到一起，因为一个形成的环一定是双连通的。然后再找两个最近公共祖先最远的两个叶节点，这样一对一对找完，恰好是(leaf+1)/2次，把所有点收缩到了一起。这道题跟pku3352一模一样，拿这个程序交两个题一个字不用改都能AC！但实际上两个题也稍有不同，这个题有一点很不容易被注意到，就是可能存在重边，两个点之间如果存在有重边，也算是双连通的。我的处理方法是在DFS时标记每条边及其反向边是否被访问过，而不是判断顶点。代码StatusAcceptedTime47msMemory376kBLength4295#include <iostream> #include <algorithm> #include <cstdio> #include <cstring> #include <stack> using namespace std; const int maxn = 5010; int n, m, tot, cnt, cccnt; int dfn[maxn], low[maxn], head[maxn], ccno[maxn], ccnum[maxn], degree[maxn]; bool vis[maxn]; struct Edge { int to, next; }edge[20010]; stack <int> S; void addedge(int u, int v) { edge[cnt].to = v; edge[cnt].next = head[u]; head[u] = cnt++; } void init() { for (int i = 0; i <= n; ++i) { dfn[i] = low[i] = ccno[i] = ccnum[i] = degree[i] = 0; head[i] = -1; vis[i] = false; } memset(edge, 0, sizeof(edge)); tot = cccnt = 0; cnt = 1; } void tarjan(int u, int father) // 求双连通分量 { low[u] = dfn[u] = ++tot; S.push(u); vis[u] = true; bool flag = true; for (int i = head[u]; i != -1; i = edge[i].next) { int v = edge[i].to; if (v == father && flag) // 重边处理 { flag = false; continue; } if (!dfn[v]) { tarjan(v, u); low[u] = min(low[u], low[v]); } else if (vis[v]) low[u] = min(low[u], dfn[v]); } if (low[u] == dfn[u]) // 栈中保存的是同一个连通分量 { cccnt++; while (1) { int v = S.top(); S.pop(); // printf("%d %d\n", cccnt, v); vis[v] = false; ccno[v] = cccnt; ccnum[cccnt]++; if (v == u) break; } } } int main() { scanf("%d%d", &n, &m); init(); int u, v; for (int i = 0; i < m; ++i) { scanf("%d%d", &u, &v); addedge(u, v); addedge(v, u); } tarjan(1, 0); for (int i = 1; i <= n; ++i) // 缩点成树求节点的度 { for (int j = head[i]; j != -1; j = edge[j].next) { int v = edge[j].to; if (ccno[i] != ccno[v]) degree[ccno[i]]++; } } int ans = 0; for (int i = 1; i <= cccnt; ++i) { if (degree[i] == 1) // 找到度为1的节点 ans++; } printf("%d\n", (ans+1) / 2); // 至少需要添加的边数 return 0; }推荐阅读lin375691011 | POJ 3352 Road Construction用Tarjan算法求双连通分量的时候，并不是low数组中值不同的就不再同一个双联通分量。很多大牛的博客都只借助low数组中的值来判断是否是同一个双联通分量。的确low数组中值相同的一定是双连通，但通过Tarjan处理过的low不同也有可能是双连通。我们开始学习Tarjan算法时有一个手写栈，每一次弹栈的时候弹出来的点是一个双联通分量才对。小優YoU | POJ3352-Road Construction若要使得任意一棵树，在增加若干条边后，变成一个双连通图，那么至少增加的边数 =（ 这棵树总度数为1的结点数 + 1 ）/ 2The end.2018-07-18 星期三
SPFTime Limit: 1000MSMemory Limit: 10000KTotal Submissions: 10137Accepted: 4541DescriptionConsider the two networks shown below. Assuming that data moves around these networks only between directly connected nodes on a peer-to-peer basis, a failure of a single node, 3, in the network on the left would prevent some of the still available nodes from communicating with each other. Nodes 1 and 2 could still communicate with each other as could nodes 4 and 5, but communication between any other pairs of nodes would no longer be possible. Node 3 is therefore a Single Point of Failure (SPF) for this network. Strictly, an SPF will be defined as any node that, if unavailable, would prevent at least one pair of available nodes from being able to communicate on what was previously a fully connected network. Note that the network on the right has no such node; there is no SPF in the network. At least two machines must fail before there are any pairs of available nodes which cannot communicate. InputThe input will contain the description of several networks. A network description will consist of pairs of integers, one pair per line, that identify connected nodes. Ordering of the pairs is irrelevant; 1 2 and 2 1 specify the same connection. All node numbers will range from 1 to 1000. A line containing a single zero ends the list of connected nodes. An empty network description flags the end of the input. Blank lines in the input file should be ignored.OutputFor each network in the input, you will output its number in the file, followed by a list of any SPF nodes that exist. The first network in the file should be identified as "Network #1", the second as "Network #2", etc. For each SPF node, output a line, formatted as shown in the examples below, that identifies the node and the number of fully connected subnets that remain when that node fails. If the network has no SPF nodes, simply output the text "No SPF nodes" instead of a list of SPF nodes.Sample Input1 2 5 4 3 1 3 2 3 4 3 5 0 1 2 2 3 3 4 4 5 5 1 0 1 2 2 3 3 4 4 6 6 3 2 5 5 1 0 0Sample OutputNetwork #1 SPF node 3 leaves 2 subnets Network #2 No SPF nodes Network #3 SPF node 2 leaves 2 subnets SPF node 3 leaves 2 subnetsSourceGreater New York 2000链接http://poj.org/problem?id=1523题意给定一个无向图，求其中的割点以及割点产生的连通分量的数量。题解Tarjan求割点，用cut[]数组记录产生的连通分量数量，输入和输出都需要特殊处理一下。求出关节点u后，还有一个问题需要解决：去掉该关节点u，将原来的连通图分成了几个连 通分量？1) 如果关节点u是根结点，则有几个子女，就分成了几个连通分量； 2) 如果关节点u不是根结点，则有d个子女w ，使得low[w]>=dfn[u]，则去掉该结点，分成了d+1个连通分量。代码StatusAcceptedMemory124kBLength2257#include <iostream> #include <cstdio> #include <cstring> #include <cmath> #include <algorithm> #include <queue> #include <stack> #include <vector> using namespace std; const int maxn = 1010; int dfn[maxn], low[maxn], cut[maxn], head[maxn]; int n, m, tot, cnt, cutcnt, rootson; struct Edge { int to, next; }edge[maxn]; void addedge(int u, int v) // 链式前向星存图 { edge[cnt].to = v; edge[cnt].next = head[u]; head[u] = cnt++; } void init() { tot = cutcnt = cnt = rootson = 0; memset(dfn, 0, sizeof(dfn)); memset(low, 0, sizeof(low)); memset(cut, 0, sizeof(cut)); memset(edge, 0, sizeof(edge)); memset(head, -1, sizeof(head)); } void tarjan(int u, int father) // 求割点 { low[u] = dfn[u] = ++tot; for (int i = head[u]; i != -1; i = edge[i].next) { int v = edge[i].to; if (!dfn[v]) { tarjan(v, u); low[u] = min(low[u], low[v]); if (low[v] >= dfn[u] && u != 1) // 判断割点条件 cut[u]++; else if (u == 1) // 判断根节点的子树数量 rootson++; } else if (v != father) low[u] = min(low[u], dfn[v]); } } int main() { // freopen("/Users/taifu/Codes/CPP/data.in", "r", stdin); // freopen("/Users/taifu/Codes/CPP/data.out","w",stdout); int u, v, kase = 0, linenum = 1; while (1) { scanf("%d", &u); if (u == 0) break; init(); scanf("%d", &v); n = u; n = max(n, max(u, v)); addedge(u, v); addedge(v, u); while (1) { scanf("%d", &u); if (u == 0) break; scanf("%d", &v); n = max(n, max(u, v)); addedge(u, v); addedge(v, u); } if (linenum > 1) // 输出最后呢一行没有空格 printf("\n"); printf("Network #%d\n", ++kase); linenum++; tarjan(1, 0); if (rootson > 1) // 为了方便后面加1，根节点产生的连通分量的在此减一 cut[1] = rootson - 1; bool flag = false; for (int i = 1; i <= n; ++i) { if (cut[i] > 0) { flag = true; printf(" SPF node %d leaves %d subnets\n", i, cut[i] + 1); } } if (!flag) printf(" No SPF nodes\n"); } return 0; }The end.2018-07-17 星期二
HDU4738 Caocao's Bridges （Tarjan求有重边的割边/桥）
Caocao's BridgesTime Limit: 2000/1000 MS (Java/Others)Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 7395Accepted Submission(s): 2270Problem DescriptionCaocao was defeated by Zhuge Liang and Zhou Yu in the battle of Chibi. But he wouldn't give up. Caocao's army still was not good at water battles, so he came up with another idea. He built many islands in the Changjiang river, and based on those islands, Caocao's army could easily attack Zhou Yu's troop. Caocao also built bridges connecting islands. If all islands were connected by bridges, Caocao's army could be deployed very conveniently among those islands. Zhou Yu couldn't stand with that, so he wanted to destroy some Caocao's bridges so one or more islands would be seperated from other islands. But Zhou Yu had only one bomb which was left by Zhuge Liang, so he could only destroy one bridge. Zhou Yu must send someone carrying the bomb to destroy the bridge. There might be guards on bridges. The soldier number of the bombing team couldn't be less than the guard number of a bridge, or the mission would fail. Please figure out as least how many soldiers Zhou Yu have to sent to complete the island seperating mission.InputThere are no more than 12 test cases.In each test case:The first line contains two integers, N and M, meaning that there are N islands and M bridges. All the islands are numbered from 1 to N. ( 2 <= N <= 1000, 0 < M <= N2 )Next M lines describes M bridges. Each line contains three integers U,V and W, meaning that there is a bridge connecting island U and island V, and there are W guards on that bridge. ( U ≠ V and 0 <= W <= 10,000 )The input ends with N = 0 and M = 0.OutputFor each test case, print the minimum soldier number Zhou Yu had to send to complete the mission. If Zhou Yu couldn't succeed any way, print -1 instead.Sample Input3 3 1 2 7 2 3 4 3 1 4 3 2 1 2 7 2 3 4 0 0Sample Output-1 4Source2013 ACM/ICPC Asia Regional Hangzhou Online链接http://acm.hdu.edu.cn/showproblem.php?pid=4738题意给定n个点m条边的无向图，现要找出该图中权值最小的桥。当删除图中的某条边e后，可将图分割成两个或两个以上的连通分量，则称边e为割边或者桥。题解求桥使用tajan算法，然后判断low[v] > dfn[u]即可。但是本题有三个需要注意的地方：如果原图本来就是不连通的，那么输出0如果求出所有桥中的最小权值为0，那么输出1，因为至少需要派一个人去炸桥有重边，这个需要进行特殊处理如何处理无向图求桥出现重边呢？可以参考这篇文章：求有重边的无向图的割边算法。自己画个图琢磨一下就出来了。如果有重边(u,v), 那么边(u,v)肯定被存了两次，所以我们只要让它第二次访问时通过就可以了。值得注意的是，边(u, fa)不是反向边，而是树边(fa, u)的第二次访问。—小白书P314。代码StatusAcceptedTime93msMemory6012kBLength1716#include <iostream> #include <cstdio> #include <cstring> #include <cmath> #include <algorithm> #include <queue> #include <stack> #include <vector> using namespace std; const int maxn = 1010; const int inf = 0x3f3f3f3f; int n, m, tot, cnt, ans, cc_cnt; int dfn[maxn], low[maxn], head[maxn]; struct Edge { int next, to, w; }edge[2*maxn*maxn]; void init() { for (int i = 0; i <= n; ++i) { low[i] = dfn[i] = 0; head[i] = -1; } tot = n; cc_cnt = cnt = 1; ans = inf; } void addedge(int u, int v, int w) { edge[cnt].to = v; edge[cnt].w = w; edge[cnt].next = head[u]; head[u] = cnt++; } void tarjan(int u, int fa) { low[u] = dfn[u] = ++tot; bool flag = true; for (int i = head[u]; i != -1; i = edge[i].next) { int v = edge[i].to; int w = edge[i].w; if (fa == v && flag) // 重边判断，只需过滤一次 { flag = false; continue; } if (!dfn[v]) { cc_cnt++; tarjan(v, u); low[u] = min(low[u], low[v]); if (low[v] > dfn[u]) // 找到最小权值 ans = min(ans, w); } else low[u] = min(low[u], dfn[v]); } } int main() { int u, v, w; while (scanf("%d%d", &n, &m) == 2 && n && m) { init(); for (int i = 0; i < m; ++i) { scanf("%d%d%d", &u, &v, &w); addedge(u, v, w); addedge(v, u, w); } tarjan(1, 0); if (cc_cnt < n) // 原图不连通 printf("0\n"); else { if (ans == 0) // “桥”上士兵为0，至少派一个人去炸桥 printf("1\n"); else printf("%d\n", (ans == inf) ? -1 : ans); // ans = inf 说明计划失败 } } return 0; }主要还是无向边是通过两条有向边来表示的，所以在要区分一下是不是反向边（回边）。测试数据来源于HDU 4738 双连通模版题。data.in3 3 1 2 7 2 3 4 3 1 4 3 2 1 2 7 2 3 4 3 4 1 2 7 2 1 7 2 3 4 3 2 4 4 3 1 2 1 1 2 3 3 4 4 4 4 1 2 1 1 2 3 3 4 4 2 4 6 4 5 1 2 1 1 2 3 3 4 4 2 4 6 1 3 0 4 5 4 3 0 3 4 4 2 4 6 2 3 0 1 3 0 2 1 1 2 0 4 2 1 2 3 1 3 5 4 5 1 2 3 2 3 4 1 3 5 4 3 7 4 3 6 4 4 1 2 3 2 3 4 1 3 5 4 3 6 4 4 1 2 4 1 3 5 4 3 6 3 4 7 6 7 1 2 1 1 3 2 2 3 3 3 4 4 4 6 5 4 5 6 5 6 7 5 6 1 2 3 1 3 4 2 3 5 3 4 7 3 5 8 5 4 9 8 9 1 8 1 5 1 2 1 7 3 1 4 4 1 2 5 4 3 6 3 2 7 5 6 8 6 7 9 6 6 1 4 1 1 2 4 2 5 4 5 6 4 3 6 4 4 3 2 6 5 1 2 4 2 5 4 5 6 4 3 6 4 4 3 2 8 10 1 8 1 5 1 2 1 7 3 1 4 4 1 2 5 4 3 6 3 2 7 5 6 8 6 7 9 8 1 2 3 3 1 2 7 1 3 1 1 3 4 0 0data.out-1 4 -1 0 4 -1 1 1 0 -1 6 4 4 -1 1 -1 2 -1 7顺便附上邝斌聚聚的板子。/* *********************************************** Author :kuangbin Created Time :2013/9/15 星期日 12:11:49 File Name :2013杭州网络赛\1001.cpp ************************************************ */ #pragma comment(linker, "/STACK:1024000000,1024000000") #include <stdio.h> #include <string.h> #include <iostream> #include <algorithm> #include <vector> #include <queue> #include <set> #include #include <string> #include <math.h> #include <stdlib.h> #include <time.h> using namespace std; const int INF = 0x3f3f3f3f; /* * 求 无向图的割点和桥 * 可以找出割点和桥，求删掉每个点后增加的连通块。 * 需要注意重边的处理，可以先用矩阵存，再转邻接表，或者进行判重 */ const int MAXN = 10010; const int MAXM = 2000010; struct Edge { int to,next; int w; bool cut;//是否为桥的标记 }edge[MAXM]; int head[MAXN],tot; int Low[MAXN],DFN[MAXN],Stack[MAXN]; int Index,top; bool Instack[MAXN]; bool cut[MAXN]; int add_block[MAXN];//删除一个点后增加的连通块 int bridge; void addedge(int u,int v,int w) { edge[tot].to = v;edge[tot].next = head[u];edge[tot].cut = false; edge[tot].w = w; head[u] = tot++; } void Tarjan(int u,int pre) { int v; Low[u] = DFN[u] = ++Index; Stack[top++] = u; Instack[u] = true; int son = 0; int pre_num = 0; for(int i = head[u];i != -1;i = edge[i].next) { v = edge[i].to; if(v == pre && pre_num == 0) { pre_num++; continue; } if( !DFN[v] ) { son++; Tarjan(v,u); if(Low[u] > Low[v])Low[u] = Low[v]; //桥 //一条无向边(u,v)是桥，当且仅当(u,v)为树枝边，且满足DFS(u)<Low(v)。 if(Low[v] > DFN[u]) { bridge++; edge[i].cut = true; edge[i^1].cut = true; } //割点 //一个顶点u是割点，当且仅当满足(1)或(2) (1) u为树根，且u有多于一个子树。 //(2) u不为树根，且满足存在(u,v)为树枝边(或称父子边， //即u为v在搜索树中的父亲)，使得DFS(u)<=Low(v) if(u != pre && Low[v] >= DFN[u])//不是树根 { cut[u] = true; add_block[u]++; } } else if( Low[u] > DFN[v]) Low[u] = DFN[v]; } //树根，分支数大于1 if(u == pre && son > 1)cut[u] = true; if(u == pre)add_block[u] = son - 1; Instack[u] = false; top--; } int solve(int N) { memset(DFN,0,sizeof(DFN)); memset(Instack,false,sizeof(Instack)); memset(add_block,0,sizeof(add_block)); memset(cut,false,sizeof(cut)); Index = top = 0; bridge = 0; for(int i = 1;i <= N;i++) if( !DFN[i] ) Tarjan(i,i); int ret = INF; for(int u = 1; u <= N;u++) for(int i = head[u]; i != -1;i = edge[i].next) if(edge[i].cut) ret = min(ret,edge[i].w); if(ret == INF)ret = -1; if(ret == 0)ret++; return ret; } int F[MAXN]; int find(int x) { if(F[x] == -1)return x; else return F[x] = find(F[x]); } void init() { memset(F,-1,sizeof(F)); tot = 0; memset(head,-1,sizeof(head)); } void bing(int u,int v) { int t1 = find(u); int t2 = find(v); if(t1 != t2)F[t1] = t2; } int main() { //freopen("in.txt","r",stdin); //freopen("out.txt","w",stdout); int n,m; while(scanf("%d%d",&n,&m) == 2) { if(n == 0 && m == 0)break; int u,v,w; init(); while(m--) { scanf("%d%d%d",&u,&v,&w); if(u == v)continue; addedge(u,v,w); addedge(v,u,w); bing(u,v); } bool flag = true; for(int i = 1; i <= n;i++) if(find(i) != find(1)) flag = false; if(!flag) { printf("0\n"); continue; } printf("%d\n",solve(n)); } return 0; }The end.2018-07-17 星期二
NetworkTime Limit: 1000MSMemory Limit: 10000KTotal Submissions: 16390Accepted: 7384DescriptionA Telephone Line Company (TLC) is establishing a new telephone cable network. They are connecting several places numbered by integers from 1 to N . No two places have the same number. The lines are bidirectional and always connect together two places and in each place the lines end in a telephone exchange. There is one telephone exchange in each place. From each place it is possible to reach through lines every other place, however it need not be a direct connection, it can go through several exchanges. From time to time the power supply fails at a place and then the exchange does not operate. The officials from TLC realized that in such a case it can happen that besides the fact that the place with the failure is unreachable, this can also cause that some other places cannot connect to each other. In such a case we will say the place (where the failure occured) is critical. Now the officials are trying to write a program for finding the number of all such critical places. Help them.InputThe input file consists of several blocks of lines. Each block describes one network. In the first line of each block there is the number of places N < 100. Each of the next at most N lines contains the number of a place followed by the numbers of some places to which there is a direct line from this place. These at most N lines completely describe the network, i.e., each direct connection of two places in the network is contained at least in one row. All numbers in one line are separated by one space. Each block ends with a line containing just 0. The last block has only one line with N = 0;OutputThe output contains for each block except the last in the input file one line containing the number of critical places.Sample Input5 5 1 2 3 4 0 6 2 1 3 5 4 6 2 0 0Sample Output1 2HintYou need to determine the end of one line.In order to make it's easy to determine,there are no extra blank before the end of each line.SourceCentral Europe 1996链接http://poj.org/problem?id=1144题意求无向图割点的数量。题解裸的Tarjan，测试一下板子，求无向图的割点和桥。对了，这题的输入有点奇葩，需要特殊处理一下。代码StatusAcceptedTime0msMemory132kBLength1463#include <iostream> #include <cstdio> #include <cstring> #include <cmath> #include <algorithm> #include <vector> #include <stack> #include <queue> using namespace std; const int maxn = 110; int dfn[maxn], low[maxn]; bool cut[maxn]; int n, cnt, tot, rootson; vector <int> E[maxn]; void init() { for (int i = 0; i <= n; ++i) { dfn[i] = low[i] = 0; cut[i] = false; E[i].clear(); } cnt = tot = rootson = 0; } void tarjan(int u, int fa) { low[u] = dfn[u] = ++tot; for (int i = 0; i < E[u].size(); ++i) { int v = E[u][i]; if (!dfn[v]) { tarjan(v, u); low[u] = min(low[u], low[v]); if (low[v] >= dfn[u] && u != 1) cut[u] = true; else if (u == 1) // 统计根节点子树的数量，数量大于2，根节点就是割点 rootson++; // if (low[v] > dfn[u]) // 桥的条件 // printf("%d %d\n", u, v); } else if (v != fa) // v是u的父亲，那么出现重边，﻿有重边那么一定不是桥，在这里为表示无向边的“第二条边”，非反向边（回边） low[u] = min(low[u], dfn[v]); // 注意dfn[v]不一定等于low[v] } } int count() { tarjan(1, 0); if (rootson > 1) // 判断根节点 cut[1] = true; for (int i = 1; i <= n; ++i) // 割点数量 if (cut[i]) cnt++; return cnt; } int main() { while (scanf("%d", &n) != EOF && n) { init(); int u, v; while (scanf("%d", &u) && u) { while (getchar() != '\n') { scanf("%d", &v); E[u].push_back(v); E[v].push_back(u); } } printf("%d\n", count()); } }才知道在vjudge交题目没有显示时间的话可能是0ms。The end.2018-07-16 星期一
Proving EquivalencesTime Limit: 4000/2000 MS (Java/Others)Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 8758Accepted Submission(s): 3110Problem DescriptionConsider the following exercise, found in a generic linear algebra textbook.Let A be an n × n matrix. Prove that the following statements are equivalent:A is invertible.Ax = b has exactly one solution for every n × 1 matrix b.Ax = b is consistent for every n × 1 matrix b.Ax = 0 has only the trivial solution x = 0.The typical way to solve such an exercise is to show a series of implications. For instance, one can proceed by showing that (a) implies (b), that (b) implies (c), that (c) implies (d), and finally that (d) implies (a). These four implications show that the four statements are equivalent.Another way would be to show that (a) is equivalent to (b) (by proving that (a) implies (b) and that (b) implies (a)), that (b) is equivalent to (c), and that (c) is equivalent to (d). However, this way requires proving six implications, which is clearly a lot more work than just proving four implications!I have been given some similar tasks, and have already started proving some implications. Now I wonder, how many more implications do I have to prove? Can you help me determine this?InputOn the first line one positive number: the number of testcases, at most 100. After that per testcase:* One line containing two integers n (1 ≤ n ≤ 20000) and m (0 ≤ m ≤ 50000): the number of statements and the number of implications that have already been proved.* m lines with two integers s1 and s2 (1 ≤ s1, s2 ≤ n and s1 ≠ s2) each, indicating that it has been proved that statement s1 implies statement s2.OutputPer testcase:* One line with the minimum number of additional implications that need to be proved in order to prove that all statements are equivalent.Sample Input2 4 0 3 2 1 2 1 3Sample Output4 2SourceNWERC 2008链接http://acm.hdu.edu.cn/showproblem.php?pid=2767题意将推导关系建图，问题转化为给出n个节点m条边的有向图，问至少还需要添加多少条边使得整个图变成一个强连通图。题解Tarjan求强连通分量缩点得到DAG，然后判断入度为0的节点的数量cnt1，出度为0的节点的数量cnt2，那么答案就是max(cnt1, cnt2)，如果整个图为一个强连通分量，那么答案就是0。具体可参考POJ1236 Network of Schools。代码StatusAcceptedTime202msMemory4152kBLength2270#include <iostream> #include <cstdio> #include <algorithm> #include <cmath> #include <cstring> #include <stack> #include <vector> #include <queue> using namespace std; const int maxn = 20010; int dfn[maxn], low[maxn], sccno[maxn], sccnum[maxn], dp[maxn], indegree[maxn], outdegree[maxn]; int n, m, tot, scccnt; bool vis[maxn]; vector <int> E[maxn]; stack <int> S; void init() { tot = scccnt = 0; for (int i = 0; i <= n; ++i) { dfn[i] = low[i] = sccno[i] = sccnum[i] = indegree[i] = outdegree[i] = 0; dp[i] = -1; vis[i] = false; E[i].clear(); } } void tarjan(int u) // 求强连通分量 { low[u] = dfn[u] = ++tot; S.push(u); vis[u] = true; for (int i = 0; i < E[u].size(); ++i) { int v = E[u][i]; if (!dfn[v]) { tarjan(v); low[u] = min(low[u], low[v]); } else if (vis[v]) low[u] = min(low[u], dfn[v]); } if (low[u] == dfn[u]) { scccnt++; while (1) { int v = S.top(); S.pop(); vis[v] = false; sccno[v] = scccnt; sccnum[scccnt]++; if (v == u) break; } } } void find_scc() { for (int i = 1; i <= n; ++i) { if (!dfn[i]) tarjan(i); } } int main() { int T, u, v; scanf("%d", &T); while (T--) { scanf("%d%d", &n, &m); init(); for (int i = 0; i < m; ++i) { scanf("%d%d", &u, &v); E[u].push_back(v); } find_scc(); for (u = 1; u <= n; ++u) // 缩点后求入度出度 { for (int i = 0; i < E[u].size(); ++i) { int v = E[u][i]; if (sccno[u] != sccno[v]) { outdegree[sccno[u]]++; indegree[sccno[v]]++; } } } int cnt1 = 0, cnt2 = 0; for (int i = 1; i <= scccnt; ++i) // 分别计算入度出度为0的点的数量 { if (indegree[i] == 0) cnt1++; if (outdegree[i] == 0) cnt2++; } if (scccnt == 1) // 整个图强连通 printf("0\n"); else printf("%d\n", max(cnt1, cnt2)); } return 0; }The end.2018-07-16 星期一
Network of SchoolsTime Limit: 1000MSMemory Limit: 10000KTotal Submissions: 21632Accepted: 8515DescriptionA number of schools are connected to a computer network. Agreements have been developed among those schools: each school maintains a list of schools to which it distributes software (the “receiving schools”). Note that if B is in the distribution list of school A, then A does not necessarily appear in the list of school B You are to write a program that computes the minimal number of schools that must receive a copy of the new software in order for the software to reach all schools in the network according to the agreement (Subtask A). As a further task, we want to ensure that by sending the copy of new software to an arbitrary school, this software will reach all schools in the network. To achieve this goal we may have to extend the lists of receivers by new members. Compute the minimal number of extensions that have to be made so that whatever school we send the new software to, it will reach all other schools (Subtask B). One extension means introducing one new member into the list of receivers of one school.InputThe first line contains an integer N: the number of schools in the network (2 <= N <= 100). The schools are identified by the first N positive integers. Each of the next N lines describes a list of receivers. The line i+1 contains the identifiers of the receivers of school i. Each list ends with a 0. An empty list contains a 0 alone in the line.OutputYour program should write two lines to the standard output. The first line should contain one positive integer: the solution of subtask A. The second line should contain the solution of subtask B.Sample Input5 2 4 3 0 4 5 0 0 0 1 0Sample Output1 2SourceIOI 1996链接http://poj.org/problem?id=1236题意给定一个n点m边有向图，问：至少选择多少个点才能从这些点到达其他所有点至少添加几条边才能从任意一点到达其他所有点题解Tarjan求强连通分量后缩点得到DAG图，设图中入度为0的点的数量为cnt1，出度为0的点的数量为cnt2，那么第一个问题的答案为cnt1，第二个问题的答案为max(cnt1, cnt2)，注意，当所有点构成一个强连通分量时，输出1和0。代码StatusAcceptedMemory716kBLength2400#include <iostream> #include <cstdio> #include <algorithm> #include <vector> #include <cstring> #include <stack> using namespace std; const int maxn = 110; vector <int> G[maxn]; int n; int tot, scc_cnt; int dfn[maxn], low[maxn], sccno[maxn], inde[maxn], outde[maxn]; bool vis[maxn]; stack <int> s; void tarjan(int x) // 求强连通分量 { dfn[x] = low[x] = ++tot; s.push(x); vis[x] = true; for (int i = 0; i < G[x].size(); ++i) { int v = G[x][i]; if (!dfn[v]) { tarjan(v); low[x] = min(low[x], low[v]); } else if (vis[v]) low[x] = min(low[x], dfn[v]); } if (dfn[x] == low[x]) { ++scc_cnt; while (1) { int u = s.top(); s.pop(); vis[u] = 0; sccno[u] = scc_cnt; if (u == x) break; } } } void find_scc() { memset(vis, 0, sizeof(vis)); memset(dfn, 0, sizeof(vis)); memset(low, 0, sizeof(low)); memset(sccno, 0, sizeof(sccno)); tot = scc_cnt = 0; for (int i = 0; i < n; ++i) if (!dfn[i]) tarjan(i); } int main() { int u; while (scanf("%d", &n) != EOF) { for (int i = 0; i <= n; ++i) G[i].clear(); for (int i = 0; i < n; ++i) { scanf("%d", &u); while (u != 0) { G[i].push_back(u-1); scanf("%d", &u); } } find_scc(); memset(inde, 0, sizeof(inde)); memset(outde, 0, sizeof(outde)); for (int u = 0; u < n; ++u) // 缩点建图 { for (int i = 0; i < G[u].size(); ++i) { int v = G[u][i]; if (sccno[u] != sccno[v]) { inde[sccno[v]]++; outde[sccno[u]]++; } } } int cnt1 = 0, cnt2 = 0; for (int i = 1; i <= scc_cnt; ++i) { if (inde[i] == 0) cnt1++; if (outde[i] == 0) cnt2++; } if (scc_cnt == 1) printf("1\n0\n"); else printf("%d\n%d\n", cnt1, max(cnt1, cnt2)); } return 0; } // freopen("/home/taifu/ACMer/Training/data.in", "r", stdin); // freopen("/home/taifu/ACMer/Training/data.out","w",stdout);这题的题意是真的难懂，看了programmy写的题解才知道题目是什么意思。The end.2018-04-26 星期四
可达性时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 262144K，其他语言524288K64bit IO Format: %lld题目描述给出一个 $0 ≤ N ≤ 10^{5}$ 点数、$0 ≤ M ≤ 10^{5}$ 点数 边数的有向图，输出一个尽可能小的点集，使得从这些点出发能够到达任意一点，如果有多个这样的集合，输出这些集合升序排序后字典序最小的。输入描述第一行为两个整数 $1 ≤ n, m ≤ 10^{5}$，接下来 M 行，每行两个整数 $1 ≤ u, v ≤ 10^{5}$ 表示从点 u 至点 v 有一条有向边。数据保证没有重边、自环。输出描述第一行输出一个整数 z，表示作为答案的点集的大小；第二行输出 z 个整数，升序排序，表示作为答案的点集。输入7 10 4 5 5 1 2 5 6 5 7 2 4 2 1 2 5 3 3 5 3 6输出2 4 7链接https://www.nowcoder.com/acm/contest/81/C题意中文题面，求一个尽可能小的点集，使得从这些点出发能够到达任意一点，要求升序排序后字典序最小。题解Tarjan模板题，求强联通分量后缩点，得到DAG图，选择每一个入度为0的强连通分量中序号最小的点。代码运行时间(ms)使用内存(KB)代码长度127179602388#include <iostream> #include <cstdio> #include <algorithm> #include <vector> #include <cstring> #include <stack> using namespace std; const int maxn = 100010; vector <int> E[maxn]; vector <int> G[maxn]; vector <int> ans; int n, m; int tot, scc_cnt; int dfn[maxn], low[maxn], sccno[maxn], inde[maxn]; bool vis[maxn]; stack <int> s; void tarjan(int x) // 求强连通分量 { dfn[x] = low[x] = ++tot; s.push(x); vis[x] = true; for (int i = 0; i < G[x].size(); ++i) { int v = G[x][i]; if (!dfn[v]) { tarjan(v); low[x] = min(low[x], low[v]); } else if (vis[v]) low[x] = min(low[x], dfn[v]); } if (dfn[x] == low[x]) { ++scc_cnt; while (1) { int u = s.top(); s.pop(); vis[u] = 0; sccno[u] = scc_cnt; E[scc_cnt].push_back(u); // 得到每一个强连通分量 if (u == x) break; } } } void find_scc() { memset(vis, 0, sizeof(vis)); memset(dfn, 0, sizeof(vis)); memset(low, 0, sizeof(low)); memset(sccno, 0, sizeof(sccno)); tot = scc_cnt = 0; for (int i = 0; i < n; ++i) if (!dfn[i]) tarjan(i); } int main() { int u, v; while (scanf("%d%d", &n, &m) != EOF) { for (int i = 0; i <= n; ++i) { G[i].clear(); E[i].clear(); } ans.clear(); for (int i = 0; i < m; ++i) { scanf("%d%d", &u, &v); u--; v--; G[u].push_back(v); } find_scc(); memset(inde, 0, sizeof(inde)); for (int u = 0; u < n; ++u) // 缩点建图 { for (int i = 0; i < G[u].size(); ++i) { int v = G[u][i]; if (sccno[u] != sccno[v]) inde[sccno[v]]++; } } for (int i = 1; i <= scc_cnt; ++i) { if (inde[i] == 0) ans.push_back(*min_element(E[i].begin(), E[i].end())); } printf("%d\n", ans.size()); printf("%d", ans[0] + 1); for (int i = 1; i < ans.size(); ++i) printf(" %d", ans[i] + 1); printf("\n"); } return 0; }The end.2018-04-26 星期四