acmicpc.net 1005(위상 정렬), 2623(위상 정렬) c++

https://www.acmicpc.net/problem/1005

저번에 정리한 위상 정렬 이론을 보면서 했더니 됬다. http://qkqhxla1.tistory.com/630

파이썬으로 짰는데 시간초과떠서 c++로 짰더니 됬다.

# -*- encoding: cp949 -*-
import Queue
answer = []
for t in xrange(int(raw_input())):
    n,k = map(int,raw_input().split())
    d = map(int,raw_input().split())
    adj = [[] for i in xrange(1001)]
    indegree = [0 for i in xrange(1001)]

    for i in xrange(k):
        a,b = map(int,raw_input().split())
        adj[a].append(b)
        indegree[b] += 1

    w = int(raw_input())
    result = [0 for i in xrange(1001)]
    q = Queue.Queue()
    for i in xrange(1,n+1):
        if indegree[i]==0:
            q.put(i)
 
    while indegree[w] > 0:
        u = q.get()
        for n in xrange(len(adj[u])):
            cur_node = adj[u][n]
            result[cur_node] = max(result[cur_node], result[u]+d[u-1])
            indegree[cur_node] -= 1
            if indegree[cur_node] == 0:
                q.put(cur_node)
        if indegree[w] <= 0:
            break
    answer.append(result[w]+d[w-1])
  
print '\n'.join(map(str,answer))

#include <iostream>
#include <queue>
using namespace std;
 
int main()
{
	int answer[1001]={0,},c=0;
	int t;
	cin>>t;
	for(int i=0;i<t;i++)
	{
		int n,k,d[1001],adj[1001][1001]={0,},indegree[1001]={0,};
		cin>>n>>k;
		for(int j=0;j<n;j++)
			cin>>d[j];

		for(int j=0;j<k;j++)
		{
			int a,b;
			cin>>a>>b;
			for(int l=0;l<1001;l++)
				if(adj[a][l]==0)
				{
					adj[a][l] = b;
					break;
				}
			indegree[b]++;
		}

		int w;
		cin>>w;
		int result[1001]={0,};
		queue<int> q;
		for(int j=1;j<n+1;j++)
			if(indegree[j]==0)
				q.push(j);
		
		while(indegree[w] > 0)
		{
			int u = q.front(); q.pop();
			int len = 0;
			for(int j=0;j<1001;j++)
				if(adj[u][j]!=0)
					len++;

			for(int n=0; n<len; n++)
			{
				int cur_node = adj[u][n];
				result[cur_node] = max(result[cur_node], result[u]+d[u-1]);
				indegree[cur_node]--;
				if(indegree[cur_node]==0)
					q.push(cur_node);
			}
			if(indegree[w] <= 0)
				break;
		}
		answer[c++] = result[w]+d[w-1];
	}
	for(int j=0;;j++)
	{
		if(answer[j]==0) break;
		cout<<answer[j]<<endl;
	}
    return 0;
}

https://www.acmicpc.net/problem/2623

위상정렬문제. 딱봐도 파이썬으로짜면 에러뜰거같아서 바로 c++로 짰다.

c++로 짤것같은 경우도 많아서 카테고리 이름을 바꿔야 하나 생각중이다.

#include <iostream>
#include <queue>
using namespace std;
 
int main()
{
	int n,m;
	int adj[1001][1001]={0,}, indegree[1001]={0,};
	cin>>n>>m; //입력부분
	for(int i=0;i<m;i++) 
	{
		int p,temp[1001]={0,};
		cin>>p;
		for(int j=0;j<p;j++)
			cin>>temp[j];
		for(int j=1;j<p;j++)
			indegree[temp[j]]++;
		for(int j=0;j<p-1;j++)
			for(int k=1;k<1001;k++)
				if(adj[temp[j]][k]==0)
				{
					adj[temp[j]][k] = temp[j+1];
					break;
				}
	}

	//for(int j=0;j<10;j++) //adj, indegree 확인용 코드
	//	cout<<indegree[j]<<" ";
	//cout<<endl<<endl;
	//for(int j=0;j<10;j++)
	//{
	//	for(int k=0;k<10;k++)
	//		cout<<adj[j][k]<<" ";
	//	cout<<endl;
	//}

	queue<int> q;
	for(int i=1;i<n+1;i++) //큐에 시작점 넣음.
		if(indegree[i]==0)
			q.push(i);

	int answer[1001]={0,},c=0;
	while(!q.empty()) //계산부
	{
		int u = q.front(); q.pop();
		int len = 0;
		answer[c++] = u;
		for(int i=1;adj[u][i]!=0;i++)
			len++;
		for(int i=1;i<len+1;i++)
		{
			indegree[adj[u][i]]--;
			if(indegree[adj[u][i]]==0)
				q.push(adj[u][i]);
		}
	}

	int l = 0; //답 길이와 n이 같으면 잘 되는거이므로 출력하고 아니면 0 출력
	for(int i=0;answer[i]!=0;i++)
		l++;
	if(l==n)
		for(int i=0;answer[i]!=0;i++)
			cout<<answer[i]<<endl;
	else
		cout<<0<<endl;
    return 0;
}