玄关2求调
查看原帖
玄关2求调
744853
FChang楼主2024/3/27 14:47
//#pragma GCC optimize(2)
//#pragma GCC optimize(3,“Ofast”,“inline”)
#include <bits/stdc++.h>
#define foR for
#define intt register int
#define zs(x) isdigit(x)
#define ll long long
#define amax max_element
#define genshin() puts("genshi over")
#define debug() puts("I AK IOI")
#define re return
using namespace std;
const int N = 4e6 + 10;

bool p[N];
int fa[N],sum[N];

int head[N],cnt;
struct node{
	int to,nxt;
}a[N];

void addedge(int u,int v) {
	a[++cnt].to = v;
	a[cnt].nxt = head[u];
	head[u] = cnt;
}

int dfn[N], low[N], dfncnt, s[N], in_stack[N], tp;
int scc[N], sc;
int sz[N],bri[N];
int dcc;

void tarjan(int u,int f) {
//	cout<<(f^1)<<"\n";
	low[u] = dfn[u] = ++dfncnt, s[++tp] = u, in_stack[u] = 1;
	for (int i = head[u]; i; i = a[i].nxt) {
		const int v = a[i].to;
		if (!dfn[v]) {
			tarjan(v,i);
			if(dfn[u] < low[v]) 
				bri[i] = bri[i ^ 1] = 1;
			low[u] = min(low[u], low[v]);
		} else if (i!=(f^1)) {
			low[u] = min(low[u], dfn[v]);
		}
	}
}

int n,m;
vector <int> ans[N];

void dfs(int x) {
	p[x] = 1;
	if(x) ans[dcc].push_back(x);
	for(intt i=head[x];i;i=a[i].nxt) {
		int v = a[i].to;
		if(p[v] || bri[i]) continue;
		dfs(v);
	}
}

int main() {
	ios::sync_with_stdio(0);
	ios_base::sync_with_stdio(0);
	cin.tie(NULL); cout.tie(NULL);
	cin>>n>>m;
	int u,v;
//	for(intt i=1;i<=n;++i) fa[i] = i;
	foR(intt i=1;i<=m;++i) {
		cin>>u>>v;
		if(u==v) continue;
		addedge(u,v);
		addedge(v,u);
	}
	for(intt i=1;i<=n;++i)
		if(!dfn[i])
			tarjan(i,0);
	for(intt i=1;i<=n;++i)
		if(!p[i]) {
			++dcc;
			dfs(i);
		}
	cout<<dcc<<"\n";
	for(intt i=1;i<=dcc;++i) {
		cout<<ans[i].size()<<" ";
		for(int j : ans[i]) cout<<j<<" ";
		cout<<"\n";
	}
	return 0;
	genshin(),debug();
}

样例3,4不对

2024/3/27 14:47
加载中...