Language: C++

/////////////         UnionFind
//    バラバラの要素を結合してグループにまとめる際に使える構造。
//    グループ番号、要素数の取得が可能だが、グループに属する要素の列挙はO(N)かかる。

class UnionFindClass {
public:
	UnionFindClass() {
		N = 0;
		parent = NULL;
		size = NULL;
	}
	~UnionFindClass() {
		if (parent != NULL) {
			delete[] parent;
		}
		if (size != NULL) {
			delete[] size;
		}
	}

	void activate(int n) {// 要素の数N
		N = n;
		parent = new int[N];
		size = new int[N];
		for (int i = 0; i < N; i++) {
			parent[i] = -1;
			size[i] = 1;
		}
	}

	inline int getParent(int x) {// グループの親の番号を得る
		if (parent[x] == -1) {
			return x;
		}
		else {
			int y = getParent(parent[x]);
			parent[x] = y;
			return y;
		}
	}
	inline int getSize(int x) {// 自分が属するグループのサイズを得る
		x = getParent(x);
		return size[x];
	}
	inline bool connect(int x, int y) {// 二つの要素を結ぶ。２グループ間を繋いだ場合trueを返す
		x = getParent(x);
		y = getParent(y);
		if (x == y) { return false; }
		int xsize = getSize(x), ysize = getSize(y);
		if (xsize < ysize) {
			parent[x] = y;
			size[y] += size[x];
			size[x] = 0;
		}
		else {
			parent[y] = x;
			size[x] += size[y];
			size[y] = 0;
		}
		return true;
	}

	//データ
	int N;// 個数
	int* parent;// 親の番号。自分自身が親なら-1。
	int* size;// 親のみ有効。自分のグループのサイズ。
};





/////////////		グラフを扱うクラス

class GraphClass {// グラフ入力を受け取る
public:
	GraphClass() {
		N = 0;
		M = 0;
		next = NULL;
		weight = NULL;
		directedFlag = false;
	}

	void activate(int n, bool directed = false) {// 頂点数nのグラフを初期化する。
		directedFlag = directed;
		N = n;
		M = 0;
		edge.clear();
		edgeActiveFlag.clear();

		if (next != NULL) { delete[] next; }
		if (weight != NULL) { delete[] weight; }
		next = new unordered_map<int, int>[N];
		weight = new ll[N];
		for (int i = 0; i < N; i++) { weight[i] = 1; }
	}
	inline void setNodeWeight(int n, ll weight) {// n番のノードの重みをweightに設定
		this->weight[n] = weight;
	}

	inline int getEdgeIndex(int x, int y) {// 辺の組からエッジの番号を得る
		if (next[x].find(y) != next[x].end()) {
			return next[x][y];
		}
		return -1;
	}
	inline void addEdge(int x, int y, ll weight = 1) {// エッジ追加
		int n = (int)edge.size();
		edge.push_back({ {x,y}, weight });
		edgeActiveFlag.push_back(true);

		next[x].insert({ y, n });

		if (directedFlag == false) {
			next[y].insert({ x, n });
		}

		M++;
	}
	inline void removeEdge(int x, int y) {// エッジ除去
		int k = getEdgeIndex(x, y);
		if (k == -1) { return; }

		x = edge[k].first.first;
		y = edge[k].first.second;

		M--;
		edgeActiveFlag[k] = false;

		next[x].erase(next[x].find(y));

		if (directedFlag == false) {
			next[y].erase(next[y].find(x));
		}
	}

	bool isTree() {// 木になっているかどうか幅優先探索で調べる
		if (N <= 0 || M != N - 1) { return false; }

		bool* visited = new bool[N];
		for (int i = 0; i < N; i++) {
			visited[i] = (i == 0);
		}

		queue<int> q; q.push(0);

		while (q.size() > 0) {
			int n = q.front(); q.pop();
			visited[n] = true;

			for (auto itr = next[n].begin(); itr != next[n].end(); itr++) {
				if (visited[itr->first] == false) {
					q.push(itr->first);
				}
			}
		}

		for (int i = 0; i < N; i++) {
			if (visited[i] == false) { delete[] visited; return false; }
		}

		delete[] visited;
		return true;
	}

	GraphClass* kruskal() {// クラスカル法によって最小全域木を構成する
		GraphClass* G = new GraphClass(); G->activate(N, directedFlag);
		UnionFindClass uf; uf.activate(N);

		vector<pair<ll, pair<int, int>>> E;
		{
			int i = 0;
			for (auto itr = edge.begin(); itr != edge.end(); itr++, i++) {
				if (edgeActiveFlag[i] == false) { continue; }
				E.push_back({ itr->second, {itr->first.first, itr->first.second} });
			}
		}

		sort(E.begin(), E.end());

		for (auto itr = E.begin(); itr != E.end(); itr++) {
			int x = itr->second.first, y = itr->second.second;
			ll w = itr->first;

			if (uf.getParent(x) != uf.getParent(y)) {
				G->addEdge(x, y, w);
				uf.connect(x, y);
			}
		}

		return G;
	}

	ll* dijkstra(int n) {// ダイクストラ法で始点nからの最短距離を得る
		if (n < 0 || n >= N) { return NULL; }

		ll* buf = new ll[N];
		for (int i = 0; i < N; i++) {
			buf[i] = 1LL << 60;
		}

		// pair<重み, 番号>を並べておく
		set<pair<ll, int>> st;

		buf[n] = 0;
		st.insert({ 0, n });

		while (st.empty() == false) {
			pair<ll, int> p = *st.begin(); st.erase(st.begin());
			int k = p.second;

			if (p.first <= buf[k]) {
				for (auto itr = next[k].begin(); itr != next[k].end(); itr++) {
					if (buf[itr->first] > buf[k] + edge[itr->second].second) {
						buf[itr->first] = buf[k] + edge[itr->second].second;
						st.insert({ buf[itr->first], itr->first });
					}
				}
			}
		}

		return buf;
	}

	ll* bellmanFord(int n) {// ベルマンフォード法で始点nからの最短距離を得る
		if (n < 0 || n >= N) { return NULL; }

		ll* buf = new ll[N];
		for (int i = 0; i < N; i++) {
			buf[i] = 1LL << 60;
		}
		buf[n] = 0;
		for (int i = 0; i < N; i++) {
			int j = 0;
			for (auto itr = edge.begin(); itr != edge.end(); itr++, j++) {
				if (edgeActiveFlag[j] == false) { continue; }
				int x = itr->first.first, y = itr->first.second;
				ll w = itr->second;

				if (buf[y] > buf[x] + w) {
					buf[y] = buf[x] + w;
					if (i == N - 1) {
						return NULL;
					}
				}
			}
		}
		return buf;
	}

	ll* getDistanceFrom(int n) {// ある点からの最短距離の表を受け取る。
		if (n < 0 || n >= N) { return NULL; }

		bool negativeFlag = false;
		{
			int i = 0;
			for (auto itr = edge.begin(); itr != edge.end(); itr++, i++) {
				if (edgeActiveFlag[i] == false) { continue; }
				if (itr->second < 0) {
					negativeFlag = true;
					break;
				}
			}
		}

		if (negativeFlag) {// 負の重みがあればベルマンフォード法
			return bellmanFord(n);
		}
		else {// 全て非負ならダイクストラ法
			return dijkstra(n);
		}
	}

	ll** getDistanceTable() {// 最短距離の表を受け取る。対角成分に非ゼロが含まれていたら、重み負の閉路が存在している。

		ll** buf = new ll * [N];
		for (int i = 0; i < N; i++) {
			buf[i] = new ll[N];
			for (int j = 0; j < N; j++) {
				buf[i][j] = 1LL << 60;
			}
			buf[i][i] = 0;
		}

		bool flag = true;
		{
			int i = 0;
			for (auto itr = edge.begin(); itr != edge.end(); itr++, i++) {
				if (itr->second < 0) { flag = false; break; }
			}
		}

		if (flag) {// 全て0以上だったらダイクストラ法を使う
			for (int i = 0; i < N; i++) {
				ll* d = getDistanceFrom(i);
				for (int j = 0; j < N; j++) {
					buf[i][j] = d[j];
				}
				delete[] d;
			}

		}
		else {// 負の重みが含まれていたらワーシャルフロイド法を使う
			for (int i = 0; i < N; i++) {
				for (auto itr = next[i].begin(); itr != next[i].end(); itr++) {
					buf[i][itr->first] = edge[itr->second].second;
				}
			}

			for (int i = 0; i < N; i++) {
				for (int j = 0; j < N; j++) {
					for (int k = 0; k < N; k++) {
						buf[j][k] = min(buf[j][k], buf[j][i] + buf[i][k]);
					}
				}
			}
		}
		return buf;
	}

	void debugCout() {// デバッグ出力用
		cout << endl;
		cout << "ノードの個数 = " << N << "個" << endl;
		cout << "エッジの本数 = " << M << "本" << endl;
		cout << endl;

		for (int i = 0; i < N; i++) {
			cout << "i = " << i << " (weight = " << weight[i] << "), 接続先 = ";
			if (next[i].size() == 0) { cout << "なし" << endl; continue; }
			auto itr = next[i].begin();
			cout << itr->first << "(weight = " << itr->second << ")";
			itr++;

			for (; itr != next[i].end(); itr++) {
				cout << ", " << itr->first << "(weight = " << itr->second << ")";
			}
			cout << endl;
		}
		cout << endl;
	}

	bool directedFlag;// 有向グラフかどうか
	int N, M;
	ll* weight;// ノードの重み
	unordered_map<int, int>* next;// 各ノードからの行き先とエッジ番号
	vector<pair<pair<int, int>, ll>> edge;// エッジ(頂点ペアと重み)
	vector<bool> edgeActiveFlag;// エッジが有効かどうか(removeを呼ぶとfalseに)
};

void bfs(GraphClass& G, int root) {// 幅優先探索
	int N = G.N;
	bool* visited = new bool[N];
	for (int i = 0; i < N; i++) {
		visited[i] = (i == root);
	}

	queue<int> q; q.push(root);

	while (q.size() > 0) {
		int n = q.front(); q.pop();
		visited[n] = true;

		// ここに各ノードで行う処理を書く

		for (auto itr = G.next[n].begin(); itr != G.next[n].end(); itr++) {

			// ここに各エッジで行う処理を書く

			if (visited[itr->first] == false) {// まだ訪れていなかったら
				q.push(itr->first);
			}
		}
	}

	delete[] visited;
}
bool* dfs_visited = NULL;
void dfs_process_main(GraphClass& G, int n, int depth) {// 深さ優先探索
	// ここに各ノードで行う処理を書く

	for (auto itr = G.next[n].begin(); itr != G.next[n].end(); itr++) {

		// ここに各エッジで行う処理を書く

		if (dfs_visited[itr->first] == false) {// まだ訪れていなかったら
			dfs_visited[itr->first] = true;
			dfs_process_main(G, itr->first, depth + 1);
			dfs_visited[itr->first] = false;
		}
	}
}
void dfs(GraphClass& G, int root) {// 深さ優先探索
	int N = G.N;
	dfs_visited = new bool[N];
	for (int i = 0; i < N; i++) { dfs_visited[i] = false; }

	dfs_visited[root] = true;
	dfs_process_main(G, root, 0);

	delete[] dfs_visited;
	dfs_visited = NULL;
}

Compiler output:
a.cc: In constructor 'UnionFindClass::UnionFindClass()':
a.cc:9:26: error: 'NULL' was not declared in this scope
    9 |                 parent = NULL;
      |                          ^~~~
a.cc:1:1: note: 'NULL' is defined in header '<cstddef>'; this is probably fixable by adding '#include <cstddef>'
  +++ |+#include <cstddef>
    1 | /////////////         UnionFind
a.cc: In destructor 'UnionFindClass::~UnionFindClass()':
a.cc:13:31: error: 'NULL' was not declared in this scope
   13 |                 if (parent != NULL) {
      |                               ^~~~
a.cc:13:31: note: 'NULL' is defined in header '<cstddef>'; this is probably fixable by adding '#include <cstddef>'
a.cc:16:29: error: 'NULL' was not declared in this scope
   16 |                 if (size != NULL) {
      |                             ^~~~
a.cc:16:29: note: 'NULL' is defined in header '<cstddef>'; this is probably fixable by adding '#include <cstddef>'
a.cc: At global scope:
a.cc:98:42: error: 'll' has not been declared
   98 |         inline void setNodeWeight(int n, ll weight) {// n番のノードの重みをweightに設定
      |                                          ^~
a.cc:108:43: error: 'll' has not been declared
  108 |         inline void addEdge(int x, int y, ll weight = 1) {// エッジ追加
      |                                           ^~
a.cc:195:9: error: 'll' does not name a type
  195 |         ll* dijkstra(int n) {// ダイクストラ法で始点nからの最短距離を得る
      |         ^~
a.cc:226:9: error: 'll' does not name a type
  226 |         ll* bellmanFord(int n) {// ベルマンフォード法で始点nからの最短距離を得る
      |         ^~
a.cc:252:9: error: 'll' does not name a type
  252 |         ll* getDistanceFrom(int n) {// ある点からの最短距離の表を受け取る。
      |         ^~
a.cc:275:9: error: 'll' does not name a type
  275 |         ll** getDistanceTable() {// 最短距離の表を受け取る。対角成分に非ゼロが含まれていたら、重み負の閉路が存在している。
      |         ^~
a.cc:345:9: error: 'll' does not name a type
  345 |         ll* weight;// ノードの重み
      |         ^~
a.cc:346:9: error: 'unordered_map' does not name a type
  346 |         unordered_map<int, int>* next;// 各ノードからの行き先とエッジ番号
      |         ^~~~~~~~~~~~~
a.cc:347:9: error: 'vector' does not name a type
  347 |         vector<pair<pair<int, int>, ll>> edge;// エッジ(頂点ペアと重み)
      |         ^~~~~~
a.cc:348:9: error: 'vector' does not name a type
  348 |         vector<bool> edgeActiveFlag;// エッジが有効かどうか(removeを呼ぶとfalseに)
      |         ^~~~~~
a.cc: In constructor 'GraphClass::GraphClass()':
a.cc:80:17: error: 'next' was not declared in this scope
   80 |                 next = NULL;
      |                 ^~~~
a.cc:80:24: error: 'NULL' was not declared in this scope
   80 |                 next = NULL;
      |                        ^~~~
a.cc:80:24: note: 'NULL' is defined in header '<cstddef>'; this is probably fixable by adding '#include <cstddef>'
a.cc:81:17: error: 'weight' was not declared in this scope
   81 |                 weight = NULL;
      |                 ^~~~~~
a.cc: In member function 'void GraphClass::activate(int, bool)':
a.cc:89:17: error: 'edge' was not declared in this scope
   89 |                 edge.clear();
      |                 ^~~~
a.cc:90:17: error: 'edgeActiveFlag' was not declared in this scope
   90 |                 edgeActiveFlag.clear();
      |                 ^~~~~~~~~~~~~~
a.cc:92:21: error: 'next' was not declared in this scope
   92 |                 if (next != NULL) { delete[] next; }
      |                     ^~~~
a.cc:92:29: error: 'NULL' was not declared in this scope
   92 |                 if (next != NULL) { delete[] next; }
      |                             ^~~~
a.cc:92:29: note: 'NULL' is defined in header '<cstddef>'; this is probably fixable by adding '#include <cstddef>'
a.cc:92:37: error: type '<type error>' argument given to 'delete', expected pointer
   92 |                 if (next != NULL) { delete[] next; }
      |                                     ^~~~~~~~~~~~~
a.cc:93:21: error: 'weight' was not declared in this scope
   93 |                 if (weight != NULL) { delete[] weight; }
      |                     ^~~~~~
a.cc:93:31: error: 'NULL' was not declared in this scope
   93 |                 if (weight != NULL) { delete[] weight; }
      |                               ^~~~
a.cc:93:31: note: 'NULL' is defined in header '<cstddef>'; this is probably fixable by adding '#include <cstddef>'
a.cc:93:39: error: type '<type error>' argument given to 'delete', expected pointer
   93 |                 if (weight != NULL) { delete[] weight; }
      |                                       ^~~~~~~~~~~~~~~
a.cc:94:17: error: 'next' was not declared in this scope
   94 |                 next = new unordered_map<int, int>[N];
      |                 ^~~~
a.cc:94:28: error: 'unordered_map' does not name a type
   94 |                 next = new unordered_map<int, int>[N];
      |                            ^~~~~~~~~~~~~
a.cc:94:42: error: expected primary-expression before 'int'
   94 |                 next = new unordered_map<int, int>[N];
      |                                          ^~~
a.cc:95:17: error: 'weight' was not declared in this scope
   95 |                 weight = new ll[N];
      |                 ^~~~~~
a.cc:95:30: error: 'll' does not name a type
   95 |                 weight = new ll[N];
      |                              ^~
a.cc: In member function 'void GraphClass::setNodeWeight(int, int)':
a.cc:99:23: error: 'class GraphClass' has no member named 'weight'
   99 |                 this->weight[n] = weight;
      |                       ^~~~~~
a.cc: In member function 'int GraphClass::getEdgeIndex(int, int)':
a.cc:103:21: error: 'next' was not declared in this scope
  103 |                 if (next[x].find(y) != next[x].end()) {
      |                     ^~~~
a.cc: In member function 'void GraphClass::addEdge(int, int, int)':
a.cc:109:30: error: 'edge' was not declared in this scope
  109 |                 int n = (int)edge.size();
      |                              ^~~~
a.cc:111:17: error: 'edgeActiveFlag' was not declared in this scope
  111 |                 edgeActiveFlag.push_back(true);
      |                 ^~~~~~~~~~~~~~
a.cc:113:17: error: 'next' was not declared in this scope
  113 |                 next[x].insert({ y, n });
      |                 ^~~~
a.cc: In member function 'void GraphClass::removeEdge(int, int)':
a.cc:125:21: error: 'edge' was not declared in this scope
  125 |                 x = edge[k].first.first;
      |                     ^~~~
a.cc:129:17: error: 'edgeActiveFlag' was not declared in this scope
  129 |                 edgeActiveFlag[k] = false;
      |                 ^~~~~~~~~~~~~~
a.cc:131:17: error: 'next' was not declared in this scope
  131 |                 next[x].erase(next[x].find(y));
      |                 ^~~~
a.cc: In member function 'bool GraphClass::isTree()':
a.cc:146:17: error: 'queue' was not declared in this scope
  146 |                 queue<int> q; q.push(0);
      |                 ^~~~~
a.cc:146:23: error: expected primary-expression before 'int'
  146 |                 queue<int> q; q.push(0);
      |                       ^~~
a.cc:146:31: error: 'q' was not declared in this scope
  146 |                 queue<int> q; q.push(0);
      |                               ^
a.cc:152:41: error: 'next' was not declared in this scope
  152 |                         for (auto itr = next[n].begin(); itr != next[n].end(); itr++) {
      |                                         ^~~~
a.cc: In member function 'GraphClass* GraphClass::kruskal()':
a.cc:171:17: error: 'vector' was not declared in this scope
  171 |                 vector<pair<ll, pair<int, int>>> E;
      |                 ^~~~~~
a.cc:171:24: error: 'pair' was not declared in this scope
  171 |                 vector<pair<ll, pair<int, int>>> E;
      |                        ^~~~
a.cc:171:29: error: 'll' was not declared in this scope
  171 |                 vector<pair<ll, pair<int, int>>> E;
      |                             ^~
a.cc:171:38: error: expected primary-expression before 'int'
  171 |                 vector<pair<ll, pair<int, int>>> E;
      |                                      ^~~
a.cc:174:41: error: 'edge' was not declared in this scope
  174 |                         for (auto itr = edge.begin(); itr != edge.end(); itr++, i++) {
      |                                         ^~~~
a.cc:175:37: error: 'edgeActiveFlag' was not declared in this scope
  175 |                                 if (edgeActiveFlag[i] == false) { continue; }
      |                                     ^~~~~~~~~~~~~~
a.cc:176:33: error: 'E' was not declared in this scope
  176 |                                 E.push_back({ itr->second, {itr->first.first, itr->first.second} });
      |                                 ^
a.cc:180:22: error: 'E' was not declared in this scope
  180 |                 sort(E.begin(), E.end());
      |                      ^
a.cc:180:17: error: 'sort' was not declared in this scope; did you mean 'short'?
  180 |                 sort(E.begin(), E.end());
      |                 ^~~~
      |                 short
a.cc:184:28: error: expected ';' before 'w'
  184 |                         ll w = itr->first;
      |                            ^
a.cc:186:61: error: 'y' was not declared in this scope
  186 |                         if (uf.getParent(x) != uf.getParent(y)) {
      |                                                             ^
a.cc:187:50: error: 'w' was not declared in this scope
  187 |                                 G->addEdge(x, y, w);
      |                                                  ^
a.cc: In member function 'void GraphClass::debugCout()':
a.cc:323:17: error: 'cout' was not declared in this scope
  323 |                 cout << endl;
      |                 ^~~~
a.cc:323:25: error: 'endl' was not declared in this scope
  323 |                 cout <<