样例过了全wa求调
查看原帖
样例过了全wa求调
823962
psh18582512217楼主2024/8/24 12:39
#include <bits/stdc++.h>
using namespace std;
#define ll long long
ll scc,inst[1000005],ti,n,m,head[1000005],cnt,dfn[1000005],low[1000005];
struct Edge{
	ll next,to;
}e[1000005];
vector<ll> ans[1000005];
void add(ll next,ll to){
	e[++cnt].to=to;
	e[cnt].next=head[next];
	head[next]=cnt;
}
stack<ll> s;
void tarjan(ll x){
	dfn[x]=low[x]=++ti;
	s.push(x);
	inst[x]=1;
	for(int i=head[x];i;i=e[i].next){
		int y=e[i].to;
		if(!dfn[y]){
			tarjan(y);
			low[x]=min(low[x],low[y]);
		}
		else if(inst[x]){
			low[x]=min(low[x],low[y]);
		}
	}
		if(dfn[x]==low[x]){
			int y;
			scc++;
			do{
				y=s.top();
				ans[scc].push_back(y);
				s.pop();
			}while(x!=y); 
			
		} 
}
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);
		}
	}
	cout<<scc<<endl;
	for(int i=1;i<=scc;i++){
		sort(ans[i].begin(),ans[i].end());
	}
	sort(ans+1,ans+scc+1);
	for(int i=1;i<=scc;i++){
		for(ll &j : ans[i]){
			cout<<j<<" ";
		}
		cout<<endl;
	}
	return 0;
}
2024/8/24 12:39
加载中...