백준 음악프로그램

문제설명

여러 묶음으로 주어지는 순서를 지키면서 전체 순서를 정하는 문제
만약 순서가 정해지지 않는다면 0을 출력!

주의점

1. 순서가 정해지지 않을 때를 구분해야함...
   그래프가 순환하는지 알아보면 된다...!
   -> dfs 사용하여 그래프 순환 확인 가능

int dfs(int x){
	
	if(visit[x]){
		if(visit[x] == -1){
			return 1;
		}
		return 0;
	}
	visit[x] = -1;
	for(set<int>::iterator iter = v[x].begin();iter!=v[x].end();iter++){
		if(dfs(*iter)){
			return 1;
		}
	}
//	for(int i=0;i<v[x].size();i++){
//		if(dfs(v[x][i])){
//			return 1;
//		}
//	}
	visit[x] = 1;
	return 0;
}

노드마다 방문하면서 -1로 바꾼 후 막히면 1로 다시 바꿔준다..

이 방식을 사용하면 순환하지는 않지만 같은 노드를 두번 반복하면서 방문 노드라고 착각하는 문제가 발생할 수 있는데 이 문제를 해결가능함

2. 그래프 연결시 1 2와 같은 연결이 두번이상 나올 수 있다..!

해결법으로

• 벡터의 중복 제거

	for(int i=1;i<=N;i++){
		sort(v[i].begin(),v[i].end());
		v[i].erase(unique(v[i].begin(),v[i].end()),v[i].end());
	}

• set 사용

	#include <set>
	set<int> v[1001];
    
    for(set<int>::iterator iter = v[num].begin();iter!=v[num].end();iter++){
			comein[*iter]--;
			if(comein[*iter]==0){
				q.push(*iter);
			}
		}

이 있는데 이 벡터 중복 제거로는 위상정렬시 사용하는 들어오는 노드 수까지 조절이 안되므로 set을 사용하여 중복을 제어해준다

코드

#include <stdio.h>
#include <vector>
#include <queue>
#include <string.h>
#include <algorithm>
#include <set>

using namespace std;
set<int> v[1001];
int comein[1001];
queue<int> q;S
int visit[1001];

//void print_all(){
//
//	for(int i=1;i<8;i++){
//		printf("%d:",i);
//		for(int j=0;j<v[i].size();j++){
//			printf("%d ",v[i][j]);
//		}
//		printf("\n");
//	}
//}
int dfs(int x){
	
	if(visit[x]){
		if(visit[x] == -1){
			return 1;
		}
		return 0;
	}
	visit[x] = -1;
	for(set<int>::iterator iter = v[x].begin();iter!=v[x].end();iter++){
		if(dfs(*iter)){
			return 1;
		}
	}
//	for(int i=0;i<v[x].size();i++){
//		if(dfs(v[x][i])){
//			return 1;
//		}
//	}
	visit[x] = 1;
	return 0;
}
int main(){
	int N,M,n;
	scanf("%d %d",&N,&M);
	for(int i=0;i<M;i++){
		scanf("%d",&n);
		int now,next;
		scanf("%d",&now);
		for(int j=1;j<n;j++){
			scanf("%d",&next);
			int bef = v[now].size();
			v[now].insert(next);
			if(bef != v[now].size()){
				comein[next]++;
			}
			
			now = next;
		}
	}
	for(int i=1;i<=N;i++){
		sort(v[i].begin(),v[i].end());
		v[i].erase(unique(v[i].begin(),v[i].end()),v[i].end());
	}
	
	for(int i=1;i<=N;i++){
		
		if(comein[i]==0){
			q.push(i);

			memset(visit,0,sizeof(visit));
			if(dfs(i)){
				printf("0");
				return 0;
			}
			//printf("\n");
			
		}
	}
	//print_all();
	while(!q.empty()){
		int num = q.front();
		printf("%d\n",num);
		for(set<int>::iterator iter = v[num].begin();iter!=v[num].end();iter++){
			comein[*iter]--;
			if(comein[*iter]==0){
				q.push(*iter);
			}
		}
		q.pop();
	}
}