样例过全wa
查看原帖
样例过全wa
1084121
lx2023211291楼主2024/3/5 17:27

dfs bfs都已经用set自动排序了,不知道哪里错

#define  _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstring>
#include <stdlib.h>
#include <stdio.h>
#include <math.h>
#include <iomanip>
#include <ctype.h>
#include <ctime>
#include <stack>
#include <list>
#include <queue>
#include <set>
#include <algorithm>
using namespace std;
const int N = 1000005;
int n, m;
int h[N], e[N], ne[N], idx;
bool st[N];

void add(int x, int y)
{
	e[idx] = y;
	ne[idx] = h[x];
	h[x] = idx++;
}

bool arr[N];

void dfs(int u)
{
	st[u] = true;
	set<int > s;
	for (int i = h[u]; i != -1; i = ne[i])
	{
		int j = e[i];
		if (!st[j])
		{
			st[j] = true;
			s.insert(j);
		}
	}
	for (set<int >::iterator iter = s.begin(); iter != s.end(); iter++)
	{
		if (u == 1 ||arr[u] == true)
		{
			cout << *iter << ' ';
			arr[*iter] = true;
		}
		dfs(*iter);
	}

}

void bfs(int k)
{
	queue<int > q;
	q.push(k);
	while (q.size())
	{
		auto t = q.front();
		q.pop();
		set<int > s;
		for (int i = h[t]; i != -1; i = ne[i])
		{
			int j = e[i];
				s.insert(j);
		}
		 
		for (set<int > ::iterator iter = s.begin(); iter != s.end(); iter++)
		{
			if (t == 1 || arr[t] == true)
			{
				if (arr[*iter] == false)
				{
					arr[*iter] = true;
					cout << *iter << ' ';
				}
			}
			q.push(*iter);
		}
	}
}

int d[N];
int main()
{
	memset(h, -1, sizeof(h));
	cin >> n >> m;
	for (int i = 0; i < m; i++)
	{
		int x, y;
		cin >> x >> y;
		add(x, y);
		d[y]++;
	}

	cout << 1 << ' ';
	for (int i = 1; i <= n; i++)
	{
		if (d[i] == 0)
		{
			dfs(i);
		}
	}
	cout << endl;
	cout << 1 << ' ';
	for (int i = 0; i <= n; i++)
	{
		arr[i] = false;
	}
	for (int i = 1; i <= n; i++)
	{
		if (d[i] == 0)
		{
			bfs(i);
		}
	}

	return 0;
}
2024/3/5 17:27
加载中...