求教j题为什么只能过百分之30呀

跪求一组hack数据

大概的思路就是每次统计入度为0的点的数量为cnt,如果cnt==1则push进ans,如果不为1则push cnt个-1进ans

#define  _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>
#include<algorithm>
#include<string.h>
#include<iostream>
#include<queue>
#include<math.h>
#include<string>
#include<map>
#include<vector>

using namespace std;

int deg[1005];
int out[1005];

int visit[1005];

vector<int>res;

vector<int>adj[1005];

queue<int>q;

int N,M;

int fa[1005];

int findx(int x)
{
	while (fa[x] != x)
	{
		x = fa[x];
	}
	return x;
}


int main(void)
{
	cin >> N >> M;

	int i;

	for (i = 1; i <= N; i++)
	{
		fa[i] = i;
	}

	for (i = 1; i <= M; i++)
	{
		int t1, t2;
		scanf("%d %d", &t1, &t2);
		
		int flags = 1;

		for (auto y : adj[t1])
		{
			if (y == t2)
			{
				flags = 0;
				break;
			}
		}
		if (flags)
		{
			adj[t1].push_back(t2);

			out[t1]++;
			deg[t2]++;

			fa[findx(t1)] = findx(t2);
		}

	}

	

	int flag = 1;
	
	for (i = 1; i <= N; i++)
	{
		if (deg[i]==0&&out[i]==0)
		{
			flag = 0;
		}

	}
	int father = findx(1);
	
	for (i = 2; i <= N; i++)
	{
		if (findx(i) != father)
		{
			flag = 0;
		}

	}



	if (!flag)
	{
		for (i = 0; i < N; i++)
		{
			res.push_back(-1);
		}
	}
	
	if (flag)
	{


		for (int i = 1; i <= N; i++)
		{
			if (deg[i] == 0)
			{
				q.push(i);
			}
		}

		int count = 0;

		while (!q.empty() && count < N)
		{
			

			int cnt = 0;

			for (i = 1; i <= N; i++)
			{
				if (visit[i])
				{
					continue;
				}
				if (deg[i] == 0)
				{
					cnt++;
					visit[i] = 1;
				}
			}
			count += cnt;
			if (cnt == 1)
			{
				int x = q.front();
				q.pop();

				res.push_back(x);

				for (auto y : adj[x])
				{
					if (--deg[y] == 0)
					{
						q.push(y);
					}
				}
			}
			else
			{
				for (i = 0; i < cnt; i++)
				{
					int th = q.front();
					q.pop();
					for (auto y : adj[th])
					{
						
						deg[y]--;
						if (deg[y] == 0)
						{
							q.push(y);
							
						}
					}
					res.push_back(-1);
				}
			}

		
		}
	}


	for (i = 0; i <N-1; i++)
	{
		printf("%d ", res[i]);
	}
	printf("%d", res[N - 1]);

	
	system("pause");
	return 0;
}

全部评论

相关推荐

昨天 11:26
清华大学 Java
打开电脑,思绪又回到了7月份刚开始的时候,感觉这个月过的如梦如幻,发生了太多事,也算是丰富了我本就是平淡的人生吧太早独立的我习惯了一切都是自己做决定,拥有绝对的决定权,而且永远不会听取别人的建议。我就是那个恋爱四年出轨的男主啦,感觉既然在牛客开了这个头,那我就要做个有始有终的人。从我出轨到结束再到和女朋友和好如初真的太像一场梦了,短短的一个月我经历了太多,也成长了很多,放下了那些本就不属于我的,找回了那些我不该放弃的。我的人生丰富且多彩,但人不能一直顺,上天总会让你的生活中出点乱子,有好有坏,让你学会一些东西,让你有成长。我和女朋友的恋爱四年太过于平淡,日常除了会制造一些小浪漫之外,我们的生活...
段哥亡命职场:不得不说,我是理解你的,你能发出来足见你是个坦诚的人,至少敢于直面自己的内心和过往的过错。 这个世界没有想象中那样非黑即白,无论是农村还是城市,在看不见的阴影里,多的是这样的事。 更多的人选择站在制高点去谩骂,一方面是社会的道德是需要制高点的,另一方面,很多人不经他人苦,却劝他人善。 大部分的我们,连自己生命的意义尚且不能明晰,道德、法律、困境,众多因果交织,人会迷失在其中,只有真的走出来之后才能看明白,可是没走出来的时候呢?谁又能保证自己能走的好,走的对呢? 可是这种问题有些人是遇不到的,不去追寻,不去探寻,也就没了这些烦恼,我总说人生的意义在过程里,没了目标也就没了过程。 限于篇幅,没法完全言明,总之,这世界是个巨大的草台班子,没什么过不去了,勇敢面对,革故鼎新才是正确,祝你早日走出来。查看图片
点赞 评论 收藏
分享
来个厂收我吧:首先,市场侧求职我不是很懂。 但是,如果hr把这份简历给我,我会觉得求职人不适合做产品经理。 问题点: 1,简历的字体格式不统一,排版不尽如人意 2,重点不突出,建议参考star法则写个人经历 3,印尼官方货币名称为印度尼西亚卢比(IDR),且GMV690000印尼盾换算为305人民币,总成交额不高。 4,右上角的意向职位在发给其他公司时记得删除。 5,你所有的经历都是新媒体运营,但是你要投市场营销岗位,jd和简历不匹配,建议用AI+提示词,参照多个jd改一下经历内容。 修改建议: 1,统一字体(中文:思源黑体或微软雅黑,英文数字:time new romans),在word中通过表格进行排版(b站学) 2,校招个人经历权重:实习经历=创业经历(大创另算)>项目经历>实训经历>校园经历 3,请将项目经历时间顺序改为倒序,最新的放最上方。 4,求职方向不同,简历文字描述侧重点也需要不同。
点赞 评论 收藏
分享
自学java狠狠赚一...:骗你点star的,港卵公司,记得把star收回去
点赞 评论 收藏
分享
评论
15
1
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务