(낙 곡 문제 표) [데이터 구조 1 - 4] 그림 의 기본 응용

P5318 [심기 18. 예 3] 문헌 방향 찾기: dfs 와 bfs, 이미 옮 겨 다 니 는 표 시 를 해 야 합 니 다. 그림 에 링 vector 의 정렬 이 존재 하기 때 문 입 니 다. sort (g. begin (), g. end ();

#include
#define ll long long
#define inf 0x3f3f3f3f
#define llinf 0x3f3f3f3f3f3f3f3f
using namespace std;
const int maxn = 100005;
vector<int> g[maxn];
int n,m;
bool vis[maxn],vis2[maxn];

void dfs(int k){
	for(int i=0;i<g[k].size();i++){
		if(!vis[g[k][i]])
		{
			cout<<g[k][i]<<" ";
			vis[g[k][i]]=1;
			dfs(g[k][i]);
		}
	}
	
}
queue<int> q;

void bfs(){
	q.push(1);
	vis2[1]=1;
	int d;
	while(!q.empty()){
		d=q.front();
		q.pop();cout<<d<<" ";
		for(int i=0;i<g[d].size();i++){
			if(!vis2[g[d][i]]){
				vis2[g[d][i]]=1;
				q.push(g[d][i]);
			}
		}
	}
	 
	
}

int main(){
	cin>>n>>m;
	int u,v;
	for(int i=1;i<=m;i++)
	{
		cin>>u>>v;
		g[u].push_back(v);
	}
	for(int i=1;i<=n;i++)sort(g[i].begin(),g[i].end());
	vis[1]=1;
	cout<<"1 ";
	dfs(1);
	cout<<endl;
	bfs();
	return 0;
}

P3916 그림 옮 겨 다 니 기
사고: 교묘 하고 역방향 으로 그림 을 만 든 다음 에 n 은 큰 것 부터 작은 것 까지 dfs 로 그림 을 옮 겨 다 니 며 매번 옮 겨 다 니 는 위치 가 최대 치 입 니 다.

#include
#define ll long long
#define inf 0x3f3f3f3f
#define llinf 0x3f3f3f3f3f3f3f3f
using namespace std;
int n,m;
const int maxn = 100005;
vector<int> g[maxn];
int f[maxn];
bool vis[maxn];

void dfs(int k,int d){
	if(f[k])return;
	f[k]=d;
	for(int i=0;i<g[k].size();i++)
		dfs(g[k][i],d);
}

int main()
{
	cin>>n>>m;
	int u,v,d;
	for(int i=1;i<=m;i++){
		cin>>u>>v;
		g[v].push_back(u);
	}
	for(int i=n;i;i--)dfs(i,i);
	for(int i=1;i<=n;i++)cout<<f[i]<<" ";
	return 0;
}