蜜汁问题?
查看原帖
蜜汁问题?
671774
LUlululu1616楼主2022/10/6 09:09

rt,以下两个代码只有第10行i的更新不一样,为什么第一个AC而第二个只有十分?

#include <bits/stdc++.h>
using namespace std;
const int maxn=1e5+5;
int n,m,in[maxn],out[maxn];
vector<int> e[maxn],vis[maxn];
int begin1[maxn];
stack<int> st;
void dfs(int now)
{
	for(int i=begin1[now];i<e[now].size();i=begin1[now])
	{
	
		begin1[now]=i+1;
		dfs(e[now][i]);
	}
	st.push(now);
}
int main()
{
	ios::sync_with_stdio(false);
	cin >>n>>m;
	for(int i=1;i<=m;i++)
	{
		int x,y;
		cin >>x>>y;
		e[x].push_back(y);
		vis[x].push_back(0);
		out[x]++,in[y]++;
	}
	bool f1=false,f2=false,f=false;
	int s=0;
	for(int i=1;i<=n;i++)
	{
		if(in[i]==out[i])
			continue;
		if(in[i]==out[i]+1)
		{
			if(f2)
				f=1;
			else
				f2=1;
		}
		else if(in[i]+1==out[i])
		{
			if(f1)
				f=1;
			else
				f1=1,s=i;
		}
		else
			f=1;
	}
	if(f)
	{
		cout <<"No"<<endl;
		return 0;
	}
	for(int i=1;i<=n;i++)
		sort(e[i].begin(),e[i].end());
	if(!f1)
		s=1;
	dfs(s);
	while(!st.empty())
	{
		cout <<st.top()<<" ";
		st.pop();
	}
	return 0;
}
#include <bits/stdc++.h>
using namespace std;
const int maxn=1e5+5;
int n,m,in[maxn],out[maxn];
vector<int> e[maxn],vis[maxn];
int begin1[maxn];
stack<int> st;
void dfs(int now)
{
	for(int i=begin1[now];i<e[now].size();i++)
	{
	
		begin1[now]=i+1;
		dfs(e[now][i]);
	}
	st.push(now);
}
int main()
{
	ios::sync_with_stdio(false);
	cin >>n>>m;
	for(int i=1;i<=m;i++)
	{
		int x,y;
		cin >>x>>y;
		e[x].push_back(y);
		vis[x].push_back(0);
		out[x]++,in[y]++;
	}
	bool f1=false,f2=false,f=false;
	int s=0;
	for(int i=1;i<=n;i++)
	{
		if(in[i]==out[i])
			continue;
		if(in[i]==out[i]+1)
		{
			if(f2)
				f=1;
			else
				f2=1;
		}
		else if(in[i]+1==out[i])
		{
			if(f1)
				f=1;
			else
				f1=1,s=i;
		}
		else
			f=1;
	}
	if(f)
	{
		cout <<"No"<<endl;
		return 0;
	}
	for(int i=1;i<=n;i++)
		sort(e[i].begin(),e[i].end());
	if(!f1)
		s=1;
	dfs(s);
	while(!st.empty())
	{
		cout <<st.top()<<" ";
		st.pop();
	}
	return 0;
}
2022/10/6 09:09
加载中...