图表可以用于看似无关的问题。假设卡片两面都有数字，你试着用一面创造一个连续的数字序列。这个问题导致了如何将一个图拆分为带圈的连通子集和不带圈的连通子集的问题。
有一些已知的算法可以检测图形是否包含圆。在这里，我们修改它以查找所有未连接到圆的节点。我们添加一个布尔数组all false，这意味着没有已知的节点连接到圆。 然后，我们在节点之间循环，应用一种常见的算法来确定一个在已知已连接到圆的节点上跳过的圆。每当我们发现一个新节点连接到一个圆，我们就会将该属性传播到所有已连接的节点，跳过已被指定为再次连接的节点。 主要功能是对“DFS算法”一文的修改 无向图中的圈检测 “:
连接到一个循环的所有节点在一个线性时间内被指定为这样。 该算法应用于最近的一个问题 挑战“锗” 大约3.5%的参与者解决了这个问题。 假设我们有N张牌（100000>=N>=1），牌的两面都有一个数字（N是无用的，可以丢弃。本着同样的精神，每辆车（N，m）：N允许我们向上放置N，并确保其在序列中的存在，而m无论如何都是无用的。 如果我们有一张卡片（n.n）：n
// the main crux of the solution, see full code belowgraph.isCyclic();int res = 1 + graph.GetAnswer();
该解决方案受到了最近相当艰难的形势的启发” 锗2018可互换性挑战赛 “并带来了金牌。
主要思想： 1.数字很大，但我们需要从1到最后一个数字的连续序列， 但数字不超过10万。所以，最大可能是10万，作为第一个假设 2.出于同样的考虑，最大数不能大于N（数的数量） 3.我们也可以通过总数字，然后取最大的，即NN。结果不能大于N或NN 4.考虑到这一点，我们可以将所有像（x，200000）这样的卡替换为（x，x）。两者都允许向上设置x，因此x不是问题。 5.两个数字都大于N或NN的卡被忽略或丢弃 6.如果卡片的两面都有相同的数字，这意味着数字总是可以的，不可能是最小的问题，所以永远不要给出答案。 7.如果有两张完全相同的卡片，比如（x，y）和（y，x），这意味着x和y都没有问题，不能成为答案 8.现在我们介绍一个主要的大想法，我们把这组卡片转换成一个图表。图中的漩涡从0到M-1进行编号，其中M是最后一个可能的数字（N中最小的，NN）。每个节点都有一些相邻的节点，所以所有边的集合都是整数向量的向量 8.将两个数字都小于或等于M的每一个卡片（x，y）放入边x-1，y-1中，因此第一个节点得到一个额外的相邻节点，反之亦然 9.由于（3，3）这样的卡片，一些漩涡将与自身相连。这是一个大小为1的环壳。 10.如果有相同的卡片，一些漩涡将由两条或更多条边连接。这是一个大小为2的环。 11.大小为1和2的回路的编号不会有任何问题。但现在我们意识到，任何长度的循环也是如此。例如，卡片是2，3；3, 4; 4, 10; 10, 2; 他们所有的数字都没有问题，只要把2，3，4，10放在上面就行了。缺点是3,4,10,2。 12.现在，如果我们有一张卡x，y，并且我们知道x已经在另一个地方得到了保证，我们可以把这张卡x放下来，y放上去，确保y在结果序列中。 12.因此，如果任何卡通过边缘连接到一个循环，它不会出现问题，因为循环都正常，所以这个数字也正常。 13.因此，如果一个包含一个循环的图中有一个相互关联的节点子集，那么所有的漩涡都不会出现任何问题。 因此，我们可以应用已知的算法之一来查找循环，如本文中所述“ 无向图中的圈检测 “加上繁殖 14.我们还可以指定图中所有连接到循环的节点，循环[]。我们可以传播这个属性 只需从循环中的一些开始，将其设置为循环，然后跳过相邻的循环，并在相邻的循环上调用相同的函数。 15.使用已知算法的组合来检测无向图中的循环，跳过已循环并传播“连接到循环”的属性，我们找到所有连接到循环的节点。所有这些节点都是安全的，它们不可能是问题 16.但如果节点不与任何循环相连，则可以简化它们的问题，但可以将其切割成没有公共边或节点的独立图。 17.但是怎么处理它们呢？它可以是一条直线分支，也可以是相互交叉的分支。所有节点都不同。 18.通过最后的努力，我们可以理解任何这样的集合只有一个有问题的数字——集合的最大值。这是可以证明的，注意交叉只会让事情变得更好，但最大值保持不变。 19.所以我们把所有不循环的部分切割成相互连接的独立实体，并在每个实体中找到最大值。 20.然后我们找到最小值，这就是最终答案！
例如：
输入：A=[1,2,4,3]B=[1,3,2,3] 产出：5。 因为卡片本身提供1，2，3，4，但不是5。
输入：A=[4,2,1,6,5]B=[3,2,1,7,7]， 产出：4。 因为你可以在第一张牌上显示3或4，但不能同时显示3和4。所以，把3放进去，1和2放在下面的牌旁边。
输入：A=[2,3]，B=[2,3] 产出：1。因为1根本不见了。
复杂性：
- 预期最坏情况时间复杂度为O（N）；
- 期望的最坏情况空间复杂度为O（N）；
最后的实施
C++
#include <algorithm> #include <vector> using namespace std; class Graph { private : int V; // No. of vertices vector<vector< int > > edges; // edges grouped by nodes bool isCyclicUtil( int v, vector< bool >& visited, int parent); vector< bool > cyclic; vector< int > maxInNonCyclicFragments; int findMax( int v); vector< bool > visitedNonCyclic; void setPropagateCycle( int v); public : Graph( int V); // Constructor void addEdge( int v, int w); // to add an edge to graph // returns true if there is a cycle and // also designates all connected to a cycle bool isCyclic(); int getSize() const { return V; } int GetAnswer(); }; Graph::Graph( int V) { this ->V = V; edges = vector<vector< int > >(V, vector< int >()); visitedNonCyclic = cyclic = vector< bool >(V, false ); } void Graph::addEdge( int v, int w) { edges[v].push_back(w); edges[w].push_back(v); } void Graph::setPropagateCycle( int v) { if (cyclic[v]) return ; cyclic[v] = true ; for ( auto i = edges[v].begin(); i != edges[v].end(); ++i) { setPropagateCycle(*i); } } bool Graph::isCyclicUtil( int v, vector< bool >& visited, int parent) { if (cyclic[v]) return true ; // Mark the current node as visited visited[v] = true ; // Recur for all the vertices edgesacent to this vertex vector< int >::iterator i; for (i = edges[v].begin(); i != edges[v].end(); ++i) { // If an edgesacent is not visited, then // recur for that edgesacent if (!visited[*i]) { if (isCyclicUtil(*i, visited, v)) { setPropagateCycle(v); return true ; } } // If an edgesacent is visited and not parent // of current vertex, then there is a cycle. else if (*i != parent) { setPropagateCycle(v); return true ; } if (cyclic[*i]) { setPropagateCycle(v); return true ; } } return false ; } bool Graph::isCyclic() { // Mark all the vortices as not visited // and not part of recursion stack vector< bool > visited(V, false ); // Call the recursive helper function // to detect cycle in different DFS trees bool res = false ; for ( int u = 0; u < V; u++) // Don't recur for u if it is already visited{ if (!visited[u] && !cyclic[u]) { if (isCyclicUtil(u, visited, -1)) { res = true ; // there was return true originally visited = vector< bool >(V, false ); } } return res; } int Graph::findMax( int v) { if (cyclic[v]) return -1; if (visitedNonCyclic.at(v)) return -1; int res = v; visitedNonCyclic.at(v) = true ; for ( auto & u2 : edges.at(v)) { res = max(res, findMax(u2)); } return res; } int Graph::GetAnswer() { // cannot be less than, after extract must add 1 int res = V; for ( int u = 0; u < V; u++) { maxInNonCyclicFragments.push_back(findMax(u)); } for ( auto & u : maxInNonCyclicFragments) { if (u >= 0) res = min(res, u); } return res; } int solution(vector< int >& A, vector< int >& B) { const int N = ( int )A.size(); const int MAX_AMOUNT = 100001; vector< bool > present(MAX_AMOUNT, false ); for ( auto & au : A) { if (au <= N) { present.at(au) = true ; } } for ( auto & au : B) { if (au <= N) { present.at(au) = true ; } } int MAX_POSSIBLE = N; for ( int i = 1; i <= N; i++) { if ( false == present.at(i)) { MAX_POSSIBLE = i - 1; break ; } } Graph graph(MAX_POSSIBLE); for ( int i = 0; i < N; i++) { if (A.at(i) > MAX_POSSIBLE && B.at(i) > MAX_POSSIBLE) { continue ; } int mi = min(A.at(i), B.at(i)); int ma = max(A.at(i), B.at(i)); if (A.at(i) > MAX_POSSIBLE || B.at(i) > MAX_POSSIBLE) { graph.addEdge(mi - 1, mi - 1); } else { graph.addEdge(mi - 1, ma - 1); } } graph.isCyclic(); int res = 1 + graph.GetAnswer(); return res; } // Test and driver #include <iostream> void test(vector< int >& A, vector< int >& B, int expected, bool printAll = false ) { int res = solution(A, B); if (expected != res || printAll) { for ( size_t i = 0; i < A.size(); i++) { cout << A.at(i) << " " ; } cout << endl; for ( size_t i = 0; i < B.size(); i++) { cout << B.at(i) << " " ; } cout << endl; if (expected != res) cout << "Error! Expected: " << expected << " " ; else cout << "Expected: " << expected << " " ; } cout << " Result: " << res << endl; } int main() { vector< int > VA; vector< int > VB; int A4[] = { 1, 1, 1, 1, 1 }; int B4[] = { 2, 3, 4, 5, 6 }; VA = vector< int >(A4, A4 + 1); VB = vector< int >(B4, B4 + 1); test(VA, VB, 2, true ); int A0[] = { 1, 1 }; int B0[] = { 2, 2 }; VA = vector< int >(A0, A0 + 2); VB = vector< int >(B0, B0 + 2); test(VA, VB, 3); int A[] = { 1, 2, 4, 3 }; int B[] = { 1, 3, 2, 3 }; VA = vector< int >(A, A + 4); VB = vector< int >(B, B + 4); test(VA, VB, 5); int A2[] = { 4, 2, 1, 6, 5 }; int B2[] = { 3, 2, 1, 7, 7 }; VA = vector< int >(A2, A2 + 5); VB = vector< int >(B2, B2 + 5); test(VA, VB, 4); int A3[] = { 2, 3 }; int B3[] = { 2, 3 }; VA = vector< int >(A3, A3 + 2); VB = vector< int >(B3, B3 + 2); test(VA, VB, 1); return 0; } |
1 2 Expected: 2 Result: 2 Result: 3 Result: 5 Result: 4 Result: 1
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
