求教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;
}

全部评论

相关推荐

07-11 22:27
中南大学 Java
程序员牛肉:学历的话没问题。但是没问题的也就只有学历了。 其实你的整体架构是正确的,博客接着干。但是项目有点过于简单了。从后端的角度上讲,你这也就是刚入门的水平,所以肯定约面试够呛。 如果你要应聘后端岗位,那你第一个项目竟然是仿写操作系统。这个你要面试官咋问你。你一定要记住一点,你简历上写的所有的东西,都是为了证明你有能力胜任当前的岗位,而不是为了证明你自己会什么。 如果你只是浅浅的做几个项目,描述也都是烂大街。技术点也都是各种混水类的配置类需求,那你就不要幻想自己能走多远。一定要保持思考,保持学习。
点赞 评论 收藏
分享
喝干太平洋:我是大专 我感觉我当时的简历比你好点 就一个vue吗
点赞 评论 收藏
分享
评论
15
1
分享

创作者周榜

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