为何RE
  • 板块灌水区
  • 楼主末然Ender
  • 当前回复2
  • 已保存回复2
  • 发布时间2024/9/8 21:17
  • 上次更新2024/9/9 12:16:04
查看原帖
为何RE
339728
末然Ender楼主2024/9/8 21:17
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
template<typename T>
void read(T& x){x=0;char ch=getchar();long long f=1;while(!isdigit(ch)){if(ch=='-')f*=-1;ch=getchar();}while(isdigit(ch)){x=x*10+ch-48;ch=getchar();}x*=f;}
template<typename T,typename... Args>
void read(T& first,Args&... args){read(first);read(args...);}
template<typename T>
void write(T arg){T x=arg;if (x<0){putchar('-');x=-x;}if(x>9){write(x/10);}putchar(x%10+'0');}
template<typename T,typename... Args>
void write(T arg,Args... args){write(arg);if(sizeof...(args) !=0){putchar(' ');write(args...);}}
const int N=1e4+5,M=1e5+5;
int dfn[N],low[N],head[N];
int Cnt;
struct edge{
	int to, nxt;
}e[M<<1]; 
void add(int f, int t)
{
	e[++Cnt].to = t;
	e[Cnt].nxt = head[f];
	head[f] = Cnt;
}
int n,m,id,cnt;
bool S[N];
int v[N];
stack<int> s;
vector<int> ans[N];
void dfs(int root){//tarjan
	low[root]=++id,dfn[root]=low[root];
	s.push(root);
	S[root]=1;
	for(int i=head[root];~i;i=e[i].nxt){
		int u=e[i].to;
		if(!dfn[u]){
			dfs(u);
			low[root]=min(low[root],low[u]);
		}
		else if(S[u]){
			low[root]=min(low[root],low[u]);
		}	
	}
	if(dfn[root]==low[root]){
		cnt++;
		ans[cnt].push_back(root);
		while(!s.empty()&&s.top()!=root){
			v[s.top()]=cnt;
			S[s.top()]=0;
			ans[cnt].push_back(s.top());
			s.pop();
		} 
		S[root]=0;
		v[root]=cnt;
		if(!s.empty())s.pop();
	}
}
bool flags[N];
int main()
{
	memset(head,-1,sizeof head);
	read(n,m);
	for(int i=1;i<=m;i++){
		int x,y;
		read(x,y);
		add(x,y);
	}
	for(int i=1;i<=n;i++){
		if(!dfn[n])dfs(n);
	}
	write(cnt);
	putchar('\n');
	for(int i=1;i<=cnt;i++){
		sort(ans[i].begin(),ans[i].end());
	}
	for(int i=1;i<=n;i++){
		if(flags[v[i]])continue;
		flags[v[i]]=1;
		for(int j=0;j<=ans[v[i]].size()-1;j++){
			write(ans[v[i]][j]);
			putchar(' ');
		}
		putchar('\n');
	}
	return 0;
}

题目:B3609

2024/9/8 21:17
加载中...