不开O2 全TLE 开了O2全WA 自己的数据和样例都能过 求调
查看原帖
不开O2 全TLE 开了O2全WA 自己的数据和样例都能过 求调
142066
秀……虚空楼主2023/9/6 16:15

求调

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e4+10;
int vis[maxn];
int dfn[maxn],low[maxn],num,n,m;
int ver[maxn],Next[maxn],head[maxn],tot,top,_stack[maxn],ins[maxn],cnt,c[maxn];
vector<int> scc[maxn];
void add(int x,int y){
	ver[++tot]=y,Next[tot]=head[x],head[x]=tot;
}
void tarjan(int x){
	dfn[x]=low[x]=++num;
	_stack[++top]=x,ins[x]=1;
	for(int i=head[x];i;i=Next[i]){
		if(!dfn[ver[i]]){
			tarjan(ver[i]);
			low[x]=min(low[x],low[ver[i]]);
		}
		else if(ins[ver[i]]){
			low[x]=min(low[x],dfn[ver[i]]);
		}
	}
	if(dfn[x]==low[x]){
		cnt++;int y;
		do{
			y=_stack[top--],ins[y]=0;
			c[y]=cnt,scc[cnt].push_back(y);
		}while(x!=y);
	}
}
int vc[maxn],nc[maxn],hc[maxn],tc;
void add_c(int x,int y){
	vc[++tc]=y,nc[tc]=hc[x],hc[x]=tc;
}
int main(){
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		int x,y;
		cin>>x>>y;
		add(x,y);
	}
	for(int i=1;i<=n;i++){
		if(!dfn[i])tarjan(i);
	}
	for(int i=1;i<=cnt;i++){
		sort(scc[i].begin(),scc[i].end());
	}
	memset(vis,0,sizeof(vis));
	cout<<cnt<<endl;
	for(int i=1;i<=n;i++){
		if(vis[c[i]])continue;
		vis[c[i]]=1;
		for(int j=0;j<scc[c[i]].size();j++){
			cout<<scc[c[i]][j]<<' ';
		}
		cout<<endl;
	}
	/*
	for(int x=1;x<=n;x++){
		for(int i=head[x];i;i=Next[i]){
			int y=ver[i];
			if(c[x]==c[y])continue;
			add_c(c[x],c[y]);
		}
	}*/

	return 0;
}
2023/9/6 16:15
加载中...