50分substack#3 4 MLE求助
查看原帖
50分substack#3 4 MLE求助
995390
codePanclA楼主2023/8/16 16:31
#include <math.h>
#include <string.h>
#include <algorithm>
#include <stack>
#include <vector>
#define ll long long
#define INF 10000001
/* run this program using the console pauser or add your own getch, system("pause") or input loop */
using namespace std;
const int N=11000000;
int n,m; 
vector<int> g[N];
stack<int> stk;
int bri[N],d[N];
int dfn[N],low[N],tot;
int cnt;
int dcc[N];
vector<int> a[N];
struct {
	int to,nxt;
}e[N];
int head[N],ct=1;
void add(int u,int v){
	e[++ct].to=v;
	e[ct].nxt=head[u];
	head[u]=ct;
}
void tarjan(int x,int edg){
	dfn[x]=low[x]=++tot;
	stk.push(x);
	for(int i=head[x];i;i=e[i].nxt){
		int v=e[i].to;
		if(!dfn[v]){
			tarjan(v,i);
			low[x]=min(low[x],low[v]);
			if(low[v]>dfn[x]){
				bri[i]=bri[i^1]=1;
			}
		}else if(i!=(edg^1)){
			low[x]=min(low[x],dfn[v]);
		}
	}
	if(dfn[x]==low[x]){
		++cnt;
		while(1){
			int y=stk.top();
			stk.pop();
			dcc[y]=cnt;
			a[cnt].push_back(y);
			if(x==y) break;
		}
	}
}
int main(int argc, char** argv) {
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		int a,b;
		cin>>a>>b;
		add(a,b);
		add(b,a);
	}
	for(int i=1;i<=n;i++){
		if(!dfn[i]){
			tarjan(i,0);
		}
	}
	cout<<cnt<<endl;
	for(int i=1;i<=cnt;i++){
	cout<<a[i].size()<<" ";
		for(int v:a[i]){
			cout<<v<<" ";
		}
		cout<<endl;
	}
	return 0;
}
2023/8/16 16:31
加载中...