求助,为啥我用vector建图50pts
查看原帖
求助,为啥我用vector建图50pts
895312
Archy_楼主2024/7/10 11:05

看了一些,我输出的边双连通分量个数大于正解,是不是哪里的判定条件少了,我看了好久,求助!!!

#include <iostream>
#include <cstdio>
#include <map>
#include <vector>
#define N 500010
#define M 2000010

using namespace std;

int n, m, low[N], dfn[N], dfncnt, bcccnt;
bool vis[N];
vector <int> g[N],ans[N];
map <pair<int,int>,bool> mp;

inline int rd() {
	int w = 1, x = 0;
    char c = getchar();
	while(c < 48 || c > 57) {
		if(c == 45) w *= -1;
		c = getchar();
	}
	while(c >= 48 && c<= 57) {
		x = (x << 1) + (x << 3) + (c ^ 48);
		c = getchar();
	}
	return x * w;
}

void tarjan(int u, int fa){
    dfn[u] = low[u] = ++dfncnt;
    for(int &v : g[u]){
        if(!dfn[v]){
            tarjan(v, u);
            low[u] = min(low[u], low[v]);
            if(low[v] > dfn[u]){
				mp[pair<int, int>(u, v)] = 1;
				mp[pair<int, int>(v, u)] = 1;
            }
        }
        else if(v != fa)low[u] = min(low[u], dfn[v]);
    }
}

void dfs(int u,int id){
    vis[u] = 1;
    ans[bcccnt].push_back(u);
    for(auto &v : g[u]){
        if(mp[pair<int, int>(u, v)] || vis[v]) continue;
        if(!vis[v]) dfs(v, id);
    }
}

int main() {
	
	n = rd(), m = rd();
	for(int i = 1;i <= m;i ++) {
		int u = rd(), v = rd();
		g[u].push_back(v);
		g[v].push_back(u);
	}
	
	for (int i = 1;i <= n;i ++)
		if (!dfn[i])
			tarjan(i, i);
			
	for(int i = 1;i <= n;i ++)
            if(!vis[i])
                dfs(i,++bcccnt);
            
	printf("%d\n",bcccnt);
	for(int i = 1;i <= bcccnt;i ++) {
		printf("%d ",ans[i].size());
		for(int &j : ans[i]) 
			printf("%d ",j);
		printf("\n");
	}
	
	return 0;
}
2024/7/10 11:05
加载中...