太傅博客 - Tarjan
type: channel
link: https://acm.taifua.com/tag/tarjan/
items: 牛客练习赛25 E 定向（Tarjan求无向图割边+dfs构造）
items: HDU3394 Railway（Tarjan求桥和点双连通分量）
items: POJ3177 Redundant Paths（Tarjan求有重边双连通分量缩点）
items: POJ3352 Road Construction（Tarjan求双连通分量缩点）
items: POJ1523 SPF（Tarjan求割点）
items: HDU4738 Caocao's Bridges （Tarjan求有重边的割边/桥）
items: POJ1144 Network（Tarjan求割点）
items: HDU2767 Proving Equivalences（Tarjan 缩点）
items: POJ1236 Network of Schools（Tarjan缩点）
items: Wannafly挑战赛14C 可达性（Tarjan 缩点）

牛客练习赛25 E 定向（Tarjan求无向图割边+dfs构造）
type: item
date: 2018-08-27T21:12:00+08:00
description: 定向时间限制：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 …

HDU3394 Railway（Tarjan求桥和点双连通分量）
type: item
date: 2018-07-18T20:20:00+08:00
description: 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)把这个大环分割成了两个小环。因为是求环,所以求的是点双连通分量。所以做法就是，求出这个无向图有多少个点双连通分量，对于每个点双连通分量，如果内…

POJ3177 Redundant Paths（Tarjan求有重边双连通分量缩点）
type: item
date: 2018-07-18T15:15:00+08:00
description: 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 fie…

POJ3352 Road Construction（Tarjan求双连通分量缩点）
type: item
date: 2018-07-18T14:56:00+08:00
description: 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. …

POJ1523 SPF（Tarjan求割点）
type: item
date: 2018-07-17T16:02:00+08:00
description: 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…

HDU4738 Caocao's Bridges （Tarjan求有重边的割边/桥）
type: item
date: 2018-07-17T14:19:00+08:00
description: 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=473…

POJ1144 Network（Tarjan求割点）
type: item
date: 2018-07-16T19:00:00+08:00
description: 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 …

HDU2767 Proving Equivalences（Tarjan 缩点）
type: item
date: 2018-07-16T14:45:00+08:00
description: 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条边的有向图，问至少还需要添加多少条边使得整个图变成一个强连通图。…

POJ1236 Network of Schools（Tarjan缩点）
type: item
date: 2018-04-26T17:23:00+08:00
description: 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…

Wannafly挑战赛14C 可达性（Tarjan 缩点）
type: item
date: 2018-04-26T15:24:00+08:00
description: 可达性时间限制：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_…