WA on #4, #5, #8, #11, #13, #22

使用 vector 存图，map 存是否是桥，然后不走桥

参考了 this 的防重边

#include<cstdio>
#include<vector>
#include<map>
#define N 500005
using namespace std;
int low[N], dfn[N], tot, n, m, vis[N], cnt[N];
int ans_tot = 0;
vector<int> G[N];
map<int, bool> flag[N];
vector<int> ans[N];
void tarjan(int u, int fa){
	low[u] = dfn[u] = ++tot;
	cnt[fa] = 0;
	for(int i = 0 ; i < G[u].size() ; i++){
		int to = G[u][i];
		if(to == fa) cnt[fa]++;
		if(vis[fa] < 2 && to == fa) continue;
		if(!dfn[to]){
			tarjan(to, u);
			low[u] = min(low[u], low[to]);
			if(dfn[u] < low[to]) {
				flag[u][to] = flag[to][u] = 1;
			}
		}
		else low[u] = min(low[u], dfn[to]); // lst: v->u; need: v->u;
	}
}
void dfs(int u){
	ans[ans_tot].push_back(u); 
	vis[u] = 1;
	for(int i = 0 ; i < G[u].size() ; i++){
		int to = G[u][i];
		if(vis[to] || flag[u][to] == 1) continue;
		dfs(to);
	}
}
int main(){
	scanf("%d%d", &n, &m);
	for(int i = 1 ; i <= m ; i++){
		int u, v;
		scanf("%d%d", &u, &v);
		G[u].push_back(v);
		G[v].push_back(u);
	}
	for(int i = 1 ; i <= n ; i++){
		if(!dfn[i]){
			tarjan(i, 0);
		}
	}
	for(int i = 1 ; i <= n ; i++){
		if(!vis[i]){
			ans_tot++;
			dfs(i);
		}
	}
	printf("%d\n", ans_tot);
	for(int i = 1 ; i <= ans_tot ; i++){
		printf("%d ", ans[i].size());
		for(int j = 0 ; j < ans[i].size() ; j++){
			printf("%d ", ans[i][j]);
		} puts("");
	}
	return 0;
}

图论好难，还是数据结构好一点