提出 #373352

---

ソースコード 拡げる

#include <iostream>
#include <stack>
#include <vector>
#include <utility>

using namespace std;

const int MAX_N = 100000;

typedef int edge;

vector<edge> g[MAX_N + 1];

int main() {
	stack<pair<int, int>> searchStack;
	int n;
	cin >> n;
	for (int i = 0; i < n; i++) {
		int a, b;
		cin >> a >> b;
		g[a].push_back(b);
		g[b].push_back(a);
	}
	
	vector<bool> visited(n + 1, false);
	vector<int> previous(n + 1, -1);
	searchStack.push(make_pair(1, -1));
	while (!searchStack.empty()) {
		pair<int, int> currentStatus = searchStack.top(); searchStack.pop();
		int currentVertex = currentStatus.first;
		int previousVertex = currentStatus.second;
		visited.at(currentVertex) = true;

		vector<edge> edges = g[currentVertex];

		// detecting loop
		bool hasLoop = false;
		int loopOriginVertex = 0;
		for (vector<edge>::iterator edgeIt = edges.begin(); edgeIt != edges.end(); ++edgeIt) {
			int nextVertex = (*edgeIt);
			if (visited.at(nextVertex) && nextVertex != previousVertex) {
				hasLoop = true;
				loopOriginVertex = nextVertex;
			}
		}
		
		if (hasLoop) {
			// counting loop length
			int loopLength = 1;
			int currentLoopVertex = currentVertex;
			while (currentLoopVertex != loopOriginVertex) {
				loopLength++;
				currentLoopVertex = previous.at(currentLoopVertex);
			}

			// output
			bool hasBranch = loopLength == n ? false : true;
			cout << (hasBranch ? 1 : 2) << " ";
			cout << n - (loopLength % 2) << endl;
			return 0;
		}

		for (vector<edge>::iterator edgeIt = edges.begin(); edgeIt != edges.end(); ++edgeIt) {
			int nextVertex = (*edgeIt);
			if (!visited.at(nextVertex)) {
				searchStack.push(make_pair(nextVertex, currentVertex));
				previous.at(nextVertex) = currentVertex;
			}
		}
	}

	return 0;
}

提出情報

ジャッジ結果