20PTS求助
查看原帖
20PTS求助
542893
tiaotiao0830楼主2023/2/12 16:09

DFS和BFS都用了,为啥只对了一个点?

#include<iostream>
#include<queue>
#include<vector>
#include<algorithm>
using namespace std;

struct Node
{
	int start;
	int end;
}graph[5000005];

bool cmp(Node x,Node y)
{
	if(x.start != y.start)
	{
		return x.start < y.start;
	}
	else
	{
		return x.end < y.end;
	}
}

vector<int> head[5000005];
int used1[5000005],used2[5000005];

void create(int start,int end)
{
	head[start].push_back(end);
}

void dfs(int start)
{
	cout << start << " ";
	for(int i = 0;i < head[start].size();i++)
	{
		if(used1[head[start][i]] == 1)
		{
			continue;
		}
		
		used1[head[start][i]] = 1;
		
		dfs(head[start][i]);
	}
}

void bfs(int start)
{
	queue<int> qlist;
	int tnode = 0;
	qlist.push(start);
	
	while(!qlist.empty())
	{
		tnode = qlist.front();
		qlist.pop();
		
		cout << tnode << " ";
		for(int i = 0;i < head[tnode].size();i++)
		{
			if(used2[head[tnode][i]])
			{
				continue;
			}
			
			used2[head[tnode][i]] = 1;
			qlist.push(head[tnode][i]);
		}	
	}	
}

int main()
{
	int n = 0,m = 0,start = 0,end = 0;
	cin >> n >> m;
	for(int i = 0;i < m;i++)
	{
		cin >> start >> end;
		graph[i].start = start;
		graph[i].end = end;
	}
	
	sort(graph,graph + n,cmp);
	
	for(int i = 0;i < n;i++)
	{
		create(graph[i].start,graph[i].end);
	}
	
	dfs(1);
	cout << endl;
	bfs(1); 
}
```cpp
2023/2/12 16:09
加载中...