RT，这题我原本用的是dfs，结果死活最后一个点TLE，还有一个点WA但这并不重要。

然后借鉴了一下一个题解的BFS写法，复杂度$O(n + m)$。但我还是没搞懂这题难道DFS不能代替BFS吗？还是我人傻常熟大？

第一份AC代码（bfs）

namespace MySolution2 {
	const int maxn = 1e5 + 5;
	int N, M, vis[maxn], h[maxn];  
	vector<int> G[maxn]; 
	vector<int> s, res; 

	int bfs(int x) {
		int tot = 0;
		queue<int> q;
		q.push(x);
		while (!q.empty()) {
			int u = q.front(); q.pop(); tot++, vis[u] = 1;
			for (int i = 0; i < sz(G[u]); i++) h[G[u][i]] = 1;
			vector<int> tmp = s; s.clear(); 
			for (int i = 0; i < sz(tmp); i++) {
				if (h[tmp[i]]) s.pb(tmp[i]);
				else q.push(tmp[i]); 
			}
			for (int i = 0; i < sz(G[u]); i++) h[G[u][i]] = 0;
		}
		return tot; 
	}

	void solve() {
		cin >> N >> M;
		for (int i = 1; i <= M; i++) {
			int u, v;
			cin >> u >> v;
			G[u].pb(v), G[v].pb(u); 
		}
		for (int i = 1; i <= N; i++) s.pb(i);
		for (int i = 1; i <= N; i++) {
			if (!vis[i]) res.pb(bfs(i)); 
		}
		sort(res.begin(), res.end()); 
		cout << sz(res) << endl; 
		for (int i = 0; i < sz(res); i++) 
			cout << res[i] - 1 << " ";
		cout << endl; 
	}
}

第二份代码（dfs）：

namespace MySolution {
	const int maxn = 1e5 + 5;
	int N, M, idx[maxn], ans[maxn], vis[maxn]; 
	vector<int> G[maxn]; 

	void dfs(int u, int k) {
		idx[u] = k;
		ans[k]++; 
		memset(vis, 0, sizeof(vis)); 
		for (int i = 0; i < sz(G[u]); i++) {
			int v = G[u][i];
			vis[v] = 1;
		}
		for (int i = 1; i <= N; i++) {
			if (!vis[i] && !idx[i]) dfs(i, k); 
		}
	}

	void solve() {
		int cnt = 0; 
		cin >> N >> M;
		for (int i = 1; i <= M; i++) {
			int u, v;
			cin >> u >> v;
			G[u].pb(v), G[v].pb(u); 
		}
		for (int i = 1; i <= N; i++) {
			if (!idx[i]) dfs(i, ++cnt); 
		}
		cout << cnt << endl; 
		sort(ans + 1, ans + cnt + 1); 
		for (int i = 1; i <= cnt; i++) 
			cout << ans[i] << " ";
		cout << endl; 
	}
}

求助大佬指点一下复杂度为何不同？谢谢啦！