每行少输出一个点???
查看原帖
每行少输出一个点???
518255
Sunflower_in_River楼主2024/10/24 15:21

每行少输出一个点,有没有大佬帮我看一下感谢不尽awa

#include<bits/stdc++.h>
using namespace std;
int n,m,ut,vt,wt,root,dfn[100010],low[100010],cnt,cntbcc;
vector<int> g[100010];
bool iscut[100010];
vector<int> cut;
vector<int> bcc[100010];
stack<int> s; 
void tarjan(int u,int fa) {
	int son = 0;
	dfn[u] = low[u] = ++cnt;
	s.push(u);//
	for (int i = 0;i < g[u].size();i ++) {
		int v = g[u][i];
		if (!dfn[v]) {
			++ son;
			tarjan(v,u);
			low[u] = min(low[u],low[v]);
			if (low[v] >= dfn[u]) {////
				++ cntbcc;
				while (s.top() != v) {////
					bcc[cntbcc].push_back(s.top());
					s.pop();
				}
				bcc[cntbcc].push_back(s.top());
				s.pop();
				bcc[cntbcc].push_back(u);
			}
		} else if (v != fa) low[u] = min(low[u],dfn[v]);
	}
	if (fa == u && son == 0) bcc[++cntbcc].push_back(u);////
	return;
}
int main() {
	scanf("%d%d",&n,&m);
	for (int i = 1;i <= m;i ++) {
		scanf("%d%d",&ut,&vt);
		g[ut].push_back(vt);
		g[vt].push_back(ut);
	}
	for (int i = 1;i <= n;i ++) {
		root = i;
		if (!dfn[i]) tarjan(i,i);
	}
	printf("%d\n",cntbcc);
	for (int i = 1;i <= cntbcc;i ++) {
		for (int j = 0;j < bcc[i].size();j ++)
			printf("%d ",bcc[i][j]);
		printf("\n");
	}
	return 0;
}

2024/10/24 15:21
加载中...