noginonoka/codeshelf

A code shelf for XCPC Template

CodeShelf

A code shelf for XCPC Template.

Author: NogiNonoka

Data: 2020 - 11 - 09

C++ CodeStyleGuide

Files

• Name as $AlgorithmName.h or $AlgorithmName.cpp

• If you defined the code as Header Files, Submit a ($AlgorithmName)_Test.cpp for test.

Headers

• Permit but Not Recommend using bits/stdc++.h;

• Do Not Use #define for Constants, using const instead;

• Do Not Use typedef for Variable Types, using template<typename > or use int and double;

Comments

• Use // or /* */;

Struct / Template Comments:

• Other Algorithms you Used in your Algorithm;

• Analyze Time and Space Complexity;

Functions / Variables Comments:

• Optional

• Use // in a Single Line;

Algorithm

• Recommend using Struct / Template for Data Structure and Algorithm;

• Use Pascal Case or Camel Case for Naming Functions in Struct;

• Add a DEBUG part / function;

• (Optional) Add a Problem ID with a Link and solve it in your main function or Independent solve function;

Constants

// Optional
#define int long long 
#define double long double
const int MAXN = ;
const int MAXE = ;
const int MOD = ;
const int INF = ;
const double eps = ;
const double PI = acos(-1);
const int DIRX[] = {};
const int DIRY[] = {};

This Constants which you Used should be defined in your Template;

Example

#include <bits/stdc++.h>
using namespace std;
// #define int long long
// #define double long double
// #define endl "\n"
// const int MAXN = ;
// const int MAXE = ;
// const int MOD = ;
// const int INF = ;
// const double eps = ;
// const double PI = acos(-1);
// const int DIRX[] = {};
// const int DIRY[] = {};

signed main(void) {
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);
    
    return 0;
}

Catalogue

CodeShelf

├─ComputationalGeometry

├─DataStructure

├─DynamicProgramming

├─GraphTheory

├─MathTheory

├─Others

└─String

codeshelf's Issues

tarjan

int dfn[MAXN], low[MAXN], belong[MAXN];
bool trav[MAXN];    //used in disconnected graph
bool vis[MAXN];
vector<int> edges[MAXN];
stack<int> s;
int cnt = 0;

void dfs(int pos, int pre) {
    static int ts = 0;   //time stamp
    vis[pos] = true;
    trav[pos] = true;   //without reset later
    s.emplace(pos);
    low[pos] = dfn[pos] = ++ts;
    for (auto &nex : edges[pos]) {
        if (dfn[nex] == 0) {
            dfs(nex, pos);
            low[pos] = min(low[pos], low[nex]);
        } else {
            if (vis[nex]) {   //&& nex != pre) {    //in undirected graph, add this
                low[pos] = min(low[pos], dfn[nex]);
            }
        }
    }
    if (low[pos] == dfn[pos] && vis[pos]) {
        ++cnt;
        while (!s.empty() && s.top() != pos) {
            belong[s.top()] = cnt;
            vis[s.top()] = false;
            s.pop();
        }
        if (!s.empty()) s.pop();
        belong[pos] = cnt; vis[pos] = false;
    }
}

//in main, to traverse a disconnected graph
for (int i = 1; i <= n; i++) {
    if (!trav[i]) dfs(i, i);
}