图怎么遍历

给出?N?个点，M?条边的有向图，对于每个点?v，求?A(v)?表示从点?v?出发，能到达的编号最大的点。

Input

第?11?行?22?个整数?,N,M，表示点数和边数。

接下来?M?行，每行?22?个整数?,Ui?,Vi?，表示边?(,)(Ui?,Vi?)。点用?1,2,…,1,2,…,N?编号。

Output

一行?N?个整数?(1),(2),…,()A(1),A(2),…,A(N)。

Sample 1

4 3
1 2
2 4
4 3

4 4 3 4

Hint

• 对于?100%100%?的数据，1≤N,M≤1e3。

• #include<iostream>
  #include<algorithm>
  #include<vector>
  #include<queue>
  #include<map>
  using namespace std;
  vector<int> a[1005];//用于储存每一个父节点包含的数据
  int ans = 0;
  bool visited[1005];//用来对已经走过的点进行标记，防止图中有环的时候陷入循环
  
  void bfs(int k) {
  	queue<int> q;//先定义一个队列
  	q.push(k);//第一项先入队
  	int t = 0;
  
  	while (q.size()) {//当它不为空的时候说明元素并没有全部遍历
  		t = q.front();
  		q.pop();//已经获取了，让他进行出栈
  		ans = max(ans, t);//每一次遇到都进行比较，找到最大的
  		for (auto& y : a[t]) {//a相当于二维数组，a[]可以看成是一个地址，所以有&，用这种方式获取a[t]中的所有
  			if (visited[y]==0) {//如果它没有经过入栈则进入
  				q.push(y);
  				visited[y] = true;//进去了就标记
  			}
  		}
  	}
  }
  
  int main() {
  	int n, m, x, y;
  	cin >> n >> m;
  
  	for (int i = 1; i <= m; i++) {
  		cin >> x >> y;
  		a[x].push_back(y);//用来将一个数对应的连接的分支储存，如a[1]里面放2 3，那么说明图中的1连接着2和3两个
  	}
  
  	for (int i = 1; i <= n; i++) {//对每一个节点遍历
  		fill(visited, visited + 1005, false);//用fill让visited中的全部内容变为false，用于从下一次的循环
  		//fill(a.begin(),a.end(),x);
  		bfs(i);
  		cout << ans << ' ';
  		ans = 0;
  	}
  
  	return 0;
  }

  运用dfs和bfs遍历图
  输入为n与第从2到n的父节点
  如5 1 1 2 3意思为2连接在1上面，3连接在1上面，4连接在2上面，5,3

• #include<iostream>
  #include<algorithm>
  #include<vector>
  #include<stack>
  #include<queue>
  using namespace std;
  int N, b[100];
  vector<int>a[100];//每一个a[i]相当于图的第几个节点，动态开辟空间，和二维数组有相似之处
  void dfs(int k)
  {
  	cout << k << ' ';//每次开始前先进行输出的操作
  	for (auto& y : a[k])//根据前一个遍历的数找到它对应的节点，直到没有分支再往上一步遍历
  		dfs(y);//进行递归操作
  }
  
  void bfs(int k)
  {
  	queue<int>q;//队列
  	q.push(k);//首元素入栈
  	while (q.size())//当队列中没有元素的时候退出
  	{
  		int x = q.front(); q.pop();//先拿到先进去的元素，再把它删除，留下来的就是下次应该往队列里堆的节点名
  		cout << x << ' ';
  		for (auto& y : a[x])//遍历将整个的所有分支全都入队列
  			q.push(y);
  	}
  }
  
  int main()
  {
  	cin >> N;
  	for (int i = 2; i <= N; i++)//因为首节点已经确定是1，那么名称从2开始
  	{
  		cin >> b[i];
  		a[b[i]].push_back(i);//把第i个放在所对应的父节点里
  	}
  	for (int i = 2; i <= N; i++)
  		sort(a[i].begin(), a[i].end());//遍历每一个父节点，把它们排成有序的
  	dfs(1);
  	cout << '\n';
  	bfs(1);
  	return 0;
  }