Submission #111850

---

Source Code Expand

#include <iostream>
#include <string>
#include <vector>
#include <list>
#include <sstream>
#include <algorithm>
#include <utility>
#include <tuple>
#include <set>
#include <map>
using namespace std;

class ABC002{
public:
	void SolveProblemD(){
		int N, M;
		cin >> N >> M;
		vector<vector<int>> k(M, vector<int>(2,0));
		for (int i = 0; i < M; ++i){
			cin >> k[i][0] >> k[i][1];
		}
		vector<list<int>> adj(N);
		for (int i = 0; i < M; ++i){
			int a = k[i][0]-1;
			int b = k[i][1]-1;
			adj[a].push_back(b);
			adj[b].push_back(a);
		}
		vector<bool> isReach(N, false);
		list<int> q;
		int max = 0;
		for (int v_s = 0; v_s < N; ++v_s){
			int count = 0;
			q.push_back(v_s);
			while (!q.empty()){
				int v_now = q.front();
				q.pop_front();
				if (!isReach[v_now]){
					// そこがまだ訪れていなければ+1
					count += 1;
					isReach[v_now] = true;
					// 行けるところを列挙qへ入れる
					for (const int& v_next : adj[v_s]){
						q.push_front(v_next);
					}
				}
			}
			if (count > max){
				max = count;
			}
		}
		cout<< max << endl;
		return;
	}
};

int main(){
	ABC002 ANS;
	ANS.SolveProblemD();
	return 0;
}

Submission Info

Judge Result