1. 隣接行列を用いたDFS（再帰実装）

class GraphStructure {
public:
    GraphStructure(int nodes);
    void addConnection(int src, int dst);
    void traverseDFS(int startNode);

private:
    int nodeCount;
    vector<vector<int>> adjacencyMatrix;
    vector<bool> visitedFlags;

    void dfsRecursive(int current);
};

GraphStructure::GraphStructure(int nodes) {
    nodeCount = nodes;
    adjacencyMatrix.resize(nodes, vector<int>(nodes, 0));
    visitedFlags.assign(nodes, false);
}

// 無向グラフ
void GraphStructure::addConnection(int src, int dst) {
    adjacencyMatrix[src][dst] = 1;
    adjacencyMatrix[dst][src] = 1; 
}

void GraphStructure::traverseDFS(int startNode) {
    fill(visitedFlags.begin(), visitedFlags.end(), false);
    dfsRecursive(startNode);
    
    for (int i = 0; i < nodeCount; i++) {
        if (!visitedFlags[i])
            dfsRecursive(i);
    }
}

void GraphStructure::dfsRecursive(int current) {
    visitedFlags[current] = true;
    cout << "ノード訪問: " << current << endl;

    for (int i = 0; i < nodeCount; i++) {
        if (adjacencyMatrix[current][i] == 1 && !visitedFlags[i]) {
            dfsRecursive(i);
        }
    }
}

2. 隣接リストを用いたDFS（スタック実装）

class GraphList {
public:
    GraphList(int nodes);
    void addEdge(int src, int dst);
    void stackDFS(int start);

private:
    int vertexCount;
    vector<vector<int>> adjacencyList;
};

GraphList::GraphList(int nodes) {
    vertexCount = nodes;
    adjacencyList.resize(nodes);
}

// 無向グラフ
void GraphList::addEdge(int src, int dst) {
    adjacencyList[src].push_back(dst);
    adjacencyList[dst].push_back(src);
}

void GraphList::stackDFS(int start) {
    vector<bool> visited(vertexCount, false);
    stack<int> traversalStack;

    visited[start] = true;
    traversalStack.push(start);

    while (!traversalStack.empty()) {
        int current = traversalStack.top();
        traversalStack.pop();
        cout << "ノード訪問: " << current << endl;

        for (int neighbor : adjacencyList[current]) {
            if (!visited[neighbor]) {
                visited[neighbor] = true;
                traversalStack.push(neighbor);
            }
        }
    }
}

3. 隣接リストを用いたBFS（キュー実装）

class GraphTraversal {
public:
    GraphTraversal(int nodes);
    void addLink(int src, int dst);
    void breadthFirstSearch(int start);

private:
    int totalNodes;
    vector<vector<int>> adjacencyList;
};

GraphTraversal::GraphTraversal(int nodes) {
    totalNodes = nodes;
    adjacencyList.resize(nodes);
}

// 無向グラフ
void GraphTraversal::addLink(int src, int dst) {
    adjacencyList[src].push_back(dst);
    adjacencyList[dst].push_back(src);
}

void GraphTraversal::breadthFirstSearch(int start) {
    vector<bool> visited(totalNodes, false);
    queue<int> searchQueue;

    visited[start] = true;
    searchQueue.push(start);

    while (!searchQueue.empty()) {
        int current = searchQueue.front();
        searchQueue.pop();
        cout << "ノード訪問: " << current << endl;

        for (int neighbor : adjacencyList[current]) {
            if (!visited[neighbor]) {
                visited[neighbor] = true;
                searchQueue.push(neighbor);
            }
        }
    }
}

4. 順方向スター構造によるDFS/BFS

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

const int MAX_VERTICES = 100000;

struct Connection {
    int destination;
    int weight;
    int nextIndex;
} connections[MAX_VERTICES];

int connectionHeads[MAX_VERTICES];
int edgeCount = 0;
int vertexTotal, edgeTotal;

void initialize() {
    fill(connectionHeads, connectionHeads + vertexTotal, -1);
    edgeCount = 0;
}

void createConnection(int from, int to, int weight) {
    connections[edgeCount].destination = to;
    connections[edgeCount].weight = weight;
    connections[edgeCount].nextIndex = connectionHeads[from];
    connectionHeads[from] = edgeCount++;
}

void depthFirst(int start) {
    vector<bool> visited(vertexTotal + 1, false);
    stack<int> dfsStack;
    
    dfsStack.push(start);
    visited[start] = true;
    
    while (!dfsStack.empty()) {
        int current = dfsStack.top();
        dfsStack.pop();
        cout << "ノード訪問: " << current << endl;
        
        for (int idx = connectionHeads[current]; idx != -1; idx = connections[idx].nextIndex) {
            int nextNode = connections[idx].destination;
            if (!visited[nextNode]) {
                dfsStack.push(nextNode);
                visited[nextNode] = true;
            }
        }
    }
}

void breadthFirst(int start) {
    vector<bool> visited(vertexTotal + 1, false);
    queue<int> bfsQueue;

    bfsQueue.push(start);
    visited[start] = true;

    while (!bfsQueue.empty()) {
        int current = bfsQueue.front();
        bfsQueue.pop();
        cout << "ノード訪問: " << current << endl;

        for (int idx = connectionHeads[current]; idx != -1; idx = connections[idx].nextIndex) {
            int nextNode = connections[idx].destination;
            if (!visited[nextNode]) {
                bfsQueue.push(nextNode);
                visited[nextNode] = true;
            }
        }
    }
}

5. 連結成分数の計算

	void countConnectedComponents() {
		visited.resize(nodeCount, false);
		componentCount = 0;

		for (int i = 0; i < nodeCount; i++) {
			if (!visited[i]) {
				recursiveDFS(i);
				componentCount++;
			}
		}
	}
	void recursiveDFS(int position) {
		visited[position] = true;
		for (int i = 0; i < nodeCount; i++) {
			if (adjacencyMatrix[position][i] == 1 && !visited[i]) {
				recursiveDFS(i);
			}
		}
	}

6. 最小全域木

最小全域木は重み付き連結無向グラフにおいて、すべての頂点を含みながら総コストが最小の部分木です。必須条件はn-1本の辺を含み、閉路を持たないこと。

Primアルゴリズム

class MinimumSpanningTree {
	int totalNodes;
	vector<vector<int>> weightedMatrix;
	map<string, int> nodeIndexMap;
	vector<int> visitedFlags;
	struct EdgeData {
		int sourceNode;
		int minimalCost;
	};

public:
	MinimumSpanningTree() {}

	void constructGraph() {
		int nodeNum;
		cin >> nodeNum;
		totalNodes = nodeNum;
		weightedMatrix.resize(totalNodes, vector<int>(totalNodes, INF));
		
		vector<string> nodeLabels(totalNodes);
		for (int i = 0; i < totalNodes; i++) {
			cin >> nodeLabels[i];
			nodeIndexMap[nodeLabels[i]] = i;
		}
		int edgeNum;
		cin >> edgeNum;
		for (int i = 0; i < edgeNum; i++) {
			string src, dst;
			int cost;
			cin >> src >> dst >> cost;
			addWeightedEdge(nodeIndexMap[src], nodeIndexMap[dst], cost);
		}
	}

	void addWeightedEdge(int src, int dst, int cost) {
		weightedMatrix[src][dst] = cost;
		weightedMatrix[dst][src] = cost;
	}

	int selectMinimum(vector<EdgeData> candidates) {
		int selectedIndex = -1, minCost = INF;
		for (int i = 0; i < totalNodes; i++) {
			if (minCost > candidates[i].minimalCost && candidates[i].minimalCost > 0) {
				minCost = candidates[i].minimalCost;
				selectedIndex = i;
			}
		}
		return selectedIndex;
	}

	void primAlgorithm(string initialNode) {
		int startIndex = nodeIndexMap[initialNode];
		int totalCost = 0;
		vector<int> selectedEdges;
		vector<EdgeData> edgeInfo(totalNodes);

		for (int i = 0; i < totalNodes; i++) {
			edgeInfo[i] = { startIndex, weightedMatrix[startIndex][i] };
		}

		edgeInfo[startIndex].minimalCost = 0;
		for (int i = 1; i < totalNodes; i++) {
			int selected = selectMinimum(edgeInfo);
			totalCost += edgeInfo[selected].minimalCost;
			selectedEdges.push_back(selected);

			edgeInfo[selected].minimalCost = 0;

			for (int j = 0; j < totalNodes; j++) {
				if (weightedMatrix[selected][j] < edgeInfo[j].minimalCost) {
					edgeInfo[j] = { selected, weightedMatrix[selected][j] };
				}
			}
		}

		cout << totalCost << endl;
		for (int i = 0; i < totalNodes - 1; i++) {
			int selected = selectedEdges[i];
			cout << nodeIndexMap[edgeInfo[selected].sourceNode] << " " << selected << " " << edgeInfo[selected].minimalCost << endl;
		}
	}
};

Kruskalアルゴリズム

class UnionFind {
	int size;
	vector<int> parentArray;
public:
	UnionFind(int size) {
		this->size = size;
		parentArray.resize(size);
		for (int i = 0; i < size; i++)
			parentArray[i] = i;
	}
	int findParent(int index) {
		if (parentArray[index] != index) return parentArray[index] = findParent(parentArray[index]);
		else return index;
	}
	void mergeSets(int first, int second) {
		parentArray[findParent(first)] = findParent(second);
		for (int i = 0; i < size; i++)
			findParent(i);
	}
	bool isSingleSet() {
		int root = parentArray[0];
		for (int i = 0; i < size; i++) {
			if (root != parentArray[i]) return false;
		}
		return true;
	}
};

class MSTKruskal {
	int totalNodes;
	vector<vector<int>> weightedMatrix;
	map<string, int> nodeIndexMap;

public:
	MSTKruskal() {}

	void constructGraph() {
		int nodeNum;
		cin >> nodeNum;
		totalNodes = nodeNum;
		weightedMatrix.resize(totalNodes, vector<int>(totalNodes, INF));
		
		vector<string> nodeLabels(totalNodes);
		for (int i = 0; i < totalNodes; i++) {
			cin >> nodeLabels[i];
			nodeIndexMap[nodeLabels[i]] = i;
		}
		int edgeNum;
		cin >> edgeNum;
		for (int i = 0; i < edgeNum; i++) {
			string src, dst;
			int cost;
			cin >> src >> dst >> cost;
			addWeightedEdge(nodeIndexMap[src], nodeIndexMap[dst], cost);
		}
	}

	void addWeightedEdge(int src, int dst, int cost) {
		weightedMatrix[src][dst] = cost;
		weightedMatrix[dst][src] = cost;
	}

	void findMinimumEdge(int &first, int &second, vector<vector<int>>& usedEdges) {
		int minCost = INF;
		for (int i = 0; i < totalNodes; i++) {
			for (int j = i+1; j < totalNodes; j++) {
				if (minCost > weightedMatrix[i][j] && usedEdges[i][j] == 0) {
					minCost = weightedMatrix[i][j];
					first = i, second = j;
				}
			}
		}
		usedEdges[first][second] = 1;
	}
	void kruskalAlgorithm(){
		vector<Edge> selectedEdges;
		vector<vector<int>> usedEdges(totalNodes, vector<int>(totalNodes,0));
		UnionFind unionFind(totalNodes);
		int totalCost = 0;

		int edgeCount = totalNodes * (totalNodes - 1) / 2;
		while (edgeCount--) {
			int u, v;
			findMinimumEdge(u, v, usedEdges);

			if (unionFind.findParent(u) != unionFind.findParent(v)) { 
				unionFind.mergeSets(u, v);
				selectedEdges.push_back({ u,v });
				totalCost += weightedMatrix[u][v];
			}
			
			if (unionFind.isSingleSet()) break;
		}
		if (!unionFind.isSingleSet()) {
			cout << -1 << endl;
		}
		else {
			cout << totalCost << endl;
			for (int i = 0; i < selectedEdges.size(); i++) {
				cout << nodeIndexMap[selectedEdges[i].from] << " " << nodeIndexMap[selectedEdges[i].to] << " " << weightedMatrix[selectedEdges[i].from][selectedEdges[i].to] << endl;
			}
		}
	}
	
};

7. 連結成分の森構築

#include <iostream>
#include <vector>
#include <stack>
using namespace std;

// 森構造ノード
struct ForestNode{
    int value;
    vector<ForestNode*> children;
    ForestNode(int val) { value = val; }
};

vector<ForestNode*> forestRoots;

class GraphStructure {
public:
    GraphStructure(int nodes);
    void addConnection(int src, int dst);
    void buildForest();
    ForestNode* recursiveDFS(int current);

private:
    int nodeCount;
    vector<vector<int>> adjacencyMatrix;
    vector<bool> visitedFlags;
};

GraphStructure::GraphStructure(int nodes) {
    nodeCount = nodes;
    adjacencyMatrix.resize(nodes, vector<int>(nodes, 0));
    visitedFlags.assign(nodes, false);
}

// 無向グラフ
void GraphStructure::addConnection(int src, int dst) {
    adjacencyMatrix[src][dst] = 1;
    adjacencyMatrix[dst][src] = 1; 
}

void GraphStructure::buildForest() {
    visitedFlags.assign(nodeCount, false);

    for (int i = 0; i < nodeCount; i++) {
        if (!visitedFlags[i]) {
            ForestNode* root = recursiveDFS(i);
            forestRoots.push_back(root);
        }
    }
}

ForestNode* GraphStructure::recursiveDFS(int current) {
    visitedFlags[current] = true;
    ForestNode* currentNode = new ForestNode(current);

    for (int i = 0; i < nodeCount; i++) {
        if (adjacencyMatrix[current][i] == 1 && !visitedFlags[i]) {
            currentNode->children.push_back(recursiveDFS(i));
        }
    }
    return currentNode;
}

void displayForest(ForestNode *node) {
    cout << node->value;
    for (int i = 0; i < node->children.size(); i++) {
        if(node != nullptr)
            displayForest(node->children[i]);
    }
}

8. 最短経路探索（Dijkstraアルゴリズム）

#include<iostream>
#include<vector>
#include<queue>
#include<stack>
#include<map>
#include<string>
#include<algorithm>
#define INF 0x3f3f3f3f
using namespace std;

class ShortestPath {
	int nodeCount;
	vector<vector<int>> weightedMatrix;
	map<string, int> nodeIndexMap;
	vector<int> visitedFlags;

public:
	ShortestPath() {}

	void constructGraph() {
		int nodeNum;
		cin >> nodeNum;
		nodeCount = nodeNum;
		weightedMatrix.assign(nodeCount, vector<int>(nodeCount));

		vector<string> nodeLabels(nodeCount);
		for (int i = 0; i < nodeCount; i++) {
			cin >> nodeLabels[i];
			nodeIndexMap[nodeLabels[i]] = i;
		}

		for (int i = 0; i < nodeCount; i++) {
			for (int j = 0; j < nodeCount; j++) {
				int weight;
				cin >> weight;
				addWeightedEdge(i, j, weight);
			}
		}
	}

	void addWeightedEdge(int src, int dst, int weight) {
		weightedMatrix[src][dst] = weight;
	}

	void dijkstraAlgorithm() {
		vector<queue<int>> pathRecords(nodeCount);
		visitedFlags.assign(nodeCount, 0);
		vector<int> distances(nodeCount, INF);

		string startNode;
		cin >> startNode;
		int start = nodeIndexMap[startNode];
		visitedFlags[start] = 1;
		distances[start] = 0;
		for (int i = 0; i < nodeCount; i++) {
			if(weightedMatrix[start][i])
			{
				distances[i] = distances[start] + weightedMatrix[start][i];
				pathRecords[i].push(start);
			}
		}

		for (int i = 0; i < nodeCount - 1; i++) {
			int minDistance = INF;
			for (int j = 0; j < nodeCount; j++)
				if (!visitedFlags[j] && minDistance > distances[j])
				{
					start = j;
					minDistance = distances[j];
				}
			visitedFlags[start] = 1;

			for (int j = 0; j < nodeCount; j++) {
				if (!visitedFlags[j] && weightedMatrix[start][j] && minDistance + weightedMatrix[start][j] < distances[j]) {
					pathRecords[j] = pathRecords[start];
					pathRecords[j].push(start);
					distances[j] = minDistance + weightedMatrix[start][j];
				}
			}
		}

		for (int i = 0; i < nodeCount; i++) {
			if (i != nodeIndexMap[startNode]) {
				cout << startNode << "-" << nodeLabels[i] << "-";
				if (distances[i] == INF) {
					cout << "-1" << endl;
				}
				else {
					cout << distances[i] << "----[";
					while(!pathRecords[i].empty()) {
						cout << nodeLabels[pathRecords[i].front()] << " ";
						pathRecords[i].pop();
					}
					cout << nodeLabels[i] << " ]" << endl;
				}
			}
		}
	}
};

9. 正の閉路検出（通貨交換問題）

#include<iostream>
#include<vector>
#include<queue>
#include<stack>
#include<map>
#include<string>
#include<algorithm>
#define INF 0x3f3f3f3f
using namespace std;

class ArbitrageDetection {
	int nodeCount;
	vector<vector<double>> exchangeRates;
	map<string, int> nodeIndexMap;
	vector<int> visitedFlags;
	vector<vector<double>> pathValues;
	bool hasArbitrage;

public:
	ArbitrageDetection() {}

	void constructGraph() {
		int nodeNum;
		cin >> nodeNum;
		nodeCount = nodeNum;
		exchangeRates.assign(nodeCount, vector<double>(nodeCount, 0));
		int edgeNum;
		cin >> edgeNum;

		vector<string> nodeLabels(nodeCount);
		for (int i = 0; i < nodeCount; i++) {
			cin >> nodeLabels[i];
			nodeIndexMap[nodeLabels[i]] = i;
		}

		for (int i = 0; i < edgeNum; i++) {
			string src, dst;
			double rate;
			cin >> src >> rate >> dst;
			addExchangeRate(nodeIndexMap[src], nodeIndexMap[dst], rate);
		}
	}

	void addExchangeRate(int src, int dst, double rate) {
		exchangeRates[src][dst] = rate;
	}


	bool detectArbitrage() {
		visitedFlags.assign(nodeCount, 0);
		pathValues.assign(nodeCount, vector<double>(nodeCount, 0));
		hasArbitrage = false;

		for (int i = 0; i < nodeCount; i++) {
			pathValues[i][i] = 1;
			for (int j = 0; j < nodeCount; j++) {
				if (i != j) pathValues[i][j] = 0;
			}
		}

		for (int i = 0; i < nodeCount; i++) {
			if (!visitedFlags[i])
				recursiveDFS(i);
			if (hasArbitrage) return true;
		}
		return false;
	}

	void recursiveDFS(int current) {
		visitedFlags[current] = 1;

		for (int i = 0; i < nodeCount; i++) {

			if (exchangeRates[current][i] && visitedFlags[i]) {  
				if (pathValues[i][current] * exchangeRates[current][i] > 1) hasArbitrage = true;
				continue;
			}
			else if(exchangeRates[current][i]){
				for (int j = 0; j < nodeCount; j++) {
					pathValues[j][i] = pathValues[j][current] * exchangeRates[current][i];
				}
				recursiveDFS(i);
			}
		}
	}
};

10. キー経路分析（AOEネットワーク）

#include<iostream>
#include<vector>
#include<queue>
#include<stack>
#include<map>
#include<string>
#include<algorithm>
#define INF 0x3f3f3f3f
using namespace std;

class CriticalPathAnalysis {
	int nodeCount;
	vector<vector<int>> activityMatrix;
	vector<int> earliestStart;
	vector<int> latestStart;
	stack<int> topologicalOrder;
	queue<int> processingQueue;
	vector<int> incomingDegrees;

public:
	CriticalPathAnalysis() {}

	void constructNetwork() {
		int nodeNum;
		cin >> nodeNum;
		nodeCount = nodeNum;
		activityMatrix.assign(nodeCount, vector<int>(nodeCount, 0));
		incomingDegrees.assign(nodeCount, 0);

		int edgeNum;
		cin >> edgeNum;
		for (int i = 0; i < edgeNum; i++) {
			int u, v, duration;
			cin >> u >> v >> duration;
			activityMatrix[u][v] = duration;
			incomingDegrees[v]++;
		}
	}

	void topologicalSort() {
		for (int i = 0; i < nodeCount; i++) {
			if (incomingDegrees[i] == 0) processingQueue.push(i);
		}
		
		earliestStart.assign(nodeCount, 0);

		while (!processingQueue.empty()) {
			int current = processingQueue.front();
			topologicalOrder.push(current);
			processingQueue.pop();
			for (int i = 0; i < nodeCount; i++) {
				if (activityMatrix[current][i] != 0) {
					incomingDegrees[i]--;
					if (incomingDegrees[i] == 0) processingQueue.push(i);
					if (earliestStart[current] + activityMatrix[current][i] > earliestStart[i]) earliestStart[i] = earliestStart[current] + activityMatrix[current][i];
				}
			}
		}

		for (int i = 0; i < nodeCount; i++) {
			cout << earliestStart[i] << " ";
		}
		cout << endl;

	}
	void identifyCriticalPath() {
		latestStart.assign(nodeCount, earliestStart[topologicalOrder.top()]); 

		while (!topologicalOrder.empty()) {
			int current = topologicalOrder.top();
			topologicalOrder.pop();
			for (int i = 0; i < nodeCount; i++) {
				if (activityMatrix[i][current] != 0) {
					if (latestStart[current] - activityMatrix[i][current] < latestStart[i]) latestStart[i] = latestStart[current] - activityMatrix[i][current];
				}
			}
		}

		for (int i = 0; i < nodeCount; i++) {
			cout << latestStart[i] << " ";
		}
		cout << endl;

		for (int i = 0; i < nodeCount; i++) {
			if (i == nodeCount - 1) cout << i << endl;
			if (earliestStart[i] == latestStart[i] && i < nodeCount - 1) cout << i << "->";
		}
	}
};

11. 旅行計画

#include<iostream>
#include<vector>
#include<queue>
#include<stack>
#include<map>
#include<string>
#include<algorithm>
#define INF 0x3f3f3f3f
using namespace std;

class TravelRoute {
	int nodeCount;
	struct Highway {
		int distance;
		int toll;
	};
	vector<vector<Highway>> roadNetwork;
	vector<int> visitedFlags;
	int sourceNode, destinationNode;

public:
	TravelRoute() {}

	void constructMap() {
		int nodeNum;
		cin >> nodeNum;
		nodeCount = nodeNum;
		roadNetwork.assign(nodeCount, vector<Highway>(nodeCount, {0,0}));

		int edgeNum;
		cin >> edgeNum;

		cin >> sourceNode >> destinationNode;

		for (int i = 0; i < edgeNum; i++) {
			int u, v, w, c;
			cin >> u >> v >> w >> c;
			addHighway(u, v, w, c);
		}
	}

	void addHighway(int src, int dst, int w, int c) {
		roadNetwork[src][dst].distance = w;
		roadNetwork[src][dst].toll = c;
	}

	void optimizeRoute() {
		vector<int> tollCosts(nodeCount, 0);
		visitedFlags.assign(nodeCount, 0);
		vector<int> distances(nodeCount, INF);

		int current = sourceNode;
		visitedFlags[current] = 1;
		distances[current] = 0;
		tollCosts[current] = 0;
		
		for (int i = 0; i < nodeCount; i++) {
			if(roadNetwork[current][i].distance)
			{
				distances[i] = distances[current] + roadNetwork[current][i].distance;
				tollCosts[i] += roadNetwork[current][i].toll;
			}
		}

		for (int i = 0; i < nodeCount - 1; i++) {
			int minDistance = INF;
			for (int j = 0; j < nodeCount; j++)
				if (!visitedFlags[j] && minDistance > distances[j])
				{
					current = j;
					minDistance = distances[j];
				}
			visitedFlags[current] = 1;

			int minToll;
			for (int j = 0; j < nodeCount; j++) {
				minToll = INF;
				if (!visitedFlags[j] && roadNetwork[current][j].distance && minDistance + roadNetwork[current][j].distance <= distances[j]) {
					if (minDistance + roadNetwork[current][j].distance == distances[j] && tollCosts[current] + roadNetwork[current][j].toll < minToll) minToll = tollCosts[current] + roadNetwork[current][j].toll;
					distances[j] = minDistance + roadNetwork[current][j].distance;
				}
				if(minToll != INF) tollCosts[j] = minToll;
			}
		}
		cout << distances[destinationNode] << " " << tollCosts[destinationNode];
	}
};

12. 007の救出（座標変換）

#include<iostream>
#include<vector>
#include<queue>
#include<stack>
#include<map>
#include<string>
#include<algorithm>
#include<cmath>
#define INF 0x3f3f3f3f
using namespace std;

class EscapeSimulation {
	int nodeCount;
	vector<vector<int>> connectivityMatrix;
	struct Coordinate {
		int x, y;
		Coordinate() {}
		Coordinate(int xx, int yy) { x = xx, y = yy; }
	};
	vector<int> visitedFlags;
	int safetyDistance;
	vector<Coordinate> positions;
	bool canEscape;

public:
	EscapeSimulation() {}

	void setupScenario() {
		int crocodileCount;
		cin >> crocodileCount;
		nodeCount = crocodileCount + 1;
		connectivityMatrix.assign(nodeCount + 1, vector<int>(nodeCount + 1, 0));
		cin >> safetyDistance;

		for (int i = 0; i < crocodileCount; i++) {
			int x, y;
			cin >> x >> y;
			positions.push_back(Coordinate{ x,y });
		}
		positions.push_back(Coordinate{ 0,0 });

		for (int i = 0; i < crocodileCount; i++) {
			for (int j = 0; j < crocodileCount; j++) {
				if (i == j || distanceBetween(positions[i], positions[j]) > safetyDistance) connectivityMatrix[i][j] = 0;
				else if (distanceBetween(positions[i], positions[j]) <= safetyDistance) {
					connectivityMatrix[i][j] = 1;
					connectivityMatrix[j][i] = 1;
				}
			}
		}
		for (int i = 0; i < crocodileCount; i++) {
			if (positions[i].x*positions[i].x + positions[i].y * positions[i].y  <= (7.5 + safetyDistance)*(7.5 + safetyDistance)) {
				connectivityMatrix[crocodileCount][i] = 1;
			}
			else {
				connectivityMatrix[crocodileCount][i] = 0;	
			}
		}
		connectivityMatrix[crocodileCount][crocodileCount] = 0;
	}

	double distanceBetween(Coordinate a, Coordinate b) {
		return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
	}

	void addConnection(int src, int dst, int value) {
		connectivityMatrix[src][dst] = value;
	}
	bool isOnShore(Coordinate p) {
		if (p.x - (-50) <= safetyDistance || 50 - p.x <= safetyDistance || p.y - (-50) <= safetyDistance || 50 - p.y <= safetyDistance) {
			return true;
		}
		else return false;
	}


	bool attemptEscape() {

		visitedFlags.assign(nodeCount, 0);
		canEscape = false;

		for (int i = 0; i < nodeCount - 1; i++)
		{
			if (!visitedFlags[i] && connectivityMatrix[nodeCount - 1][i])  
			{
				recursiveDFS(i);
			}
			if (canEscape) return true;
		}
		return false;
	}

	void recursiveDFS(int current) {
		visitedFlags[current] = 1;
		if (isOnShore(positions[current]) || canEscape)
		{
			canEscape = true; return;
		}
		for (int i = 0; i < nodeCount - 1; i++)
		{
			if (!visitedFlags[i] && connectivityMatrix[current][i])
			{
				recursiveDFS(i);
			}
		}

	}
};

13. サイクル検出

無向グラフ: 度数1の頂点を順に削除し、関連頂点の度数を減らす。最終的に度数>1の頂点が存在すればサイクルあり。

有向グラフ: 入次数0の頂点を順に削除し、関連頂点の入次数を減らす。最終的に入次数≠0の頂点が存在すればサイクルあり。

// 無向グラフのサイクル検出

#include<bits/stdc++.h>
#define MAX_NODES 100010
using namespace std;

vector<vector<int>> graph;
int nodeCount;
vector<int> degrees;

int main()
{
    cin >> nodeCount;
    degrees.resize(nodeCount + 1, 0);
    graph.resize(nodeCount + 1);
    for (int i = 1; i <= nodeCount; i++) {
        int a, b;
        cin >> a >> b;
        degrees[a]++, degrees[b]++;
        graph[a].push_back(b);
        graph[b].push_back(a);
    }

    queue<int> leafNodes;
    for (int i = 1; i <= nodeCount; i++) {
        if (degrees[i] == 1) leafNodes.push(i);
    }
    while (!leafNodes.empty()) {
        int current = leafNodes.front();
        leafNodes.pop();
        for (int i = 0; i < graph[current].size(); i++) {
            int connected = graph[current][i];
            degrees[connected]--;
            if (degrees[connected] == 1) {
                leafNodes.push(connected);
            }
        }
    }
    for (int i = 1; i <= nodeCount; i++) {
        if (degrees[i] > 1) cout << i << " ";
    }
    return 0;
}