Need help with Topological Sorting

Hello, I am currently solving this problem on topological sorting: https://train.nzoi.org.nz/problems/475

However, my solution doesn't seem to be accepted.

Can someone please tell me what's wrong with my code?

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <stack>

using namespace std;

vector<bool> visited(30, false);
stack<int> list;

//The dfs algorithm
void dfs(vector<vector<int> > adj, int c)
{
	visited[c] = true;
	
	int size = adj[c].size();
	for (int i = size - 1; i > 0; i--)
	{
		int j = adj[c][i];
		if (!visited[j])
		{
			dfs(adj, j);
		}
	}

	list.push(c);
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	//Input number of tasks
	int N;
	cin >> N;
	cin.ignore();

	//Input the instructions
	vector<string> s(N);
	for (int i = 0; i < N; i++)
	{
		getline(cin, s[i]);
	}

	//Input the vertexes for graph and put into adjacency list
	vector<int> temp;
	vector<vector<int> > adj(N, vector<int>(1));
	int a, b;
	while (cin >> a >> b)
	{
		adj[a].push_back(b);
		temp.push_back(b);
	}

	//Sort each adjacency list
	for (int i = 0; i < N; i++)
	{
		if (!adj[i].empty())
		{
			sort(adj[i].begin(), adj[i].end());
		}
	}

	//Find the first in-degree vertex and do dfs on it
	sort(temp.begin(), temp.end());
	temp.erase(unique(temp.begin(), temp.end()), temp.end());

	int count = 0;
	for (int i = N - 1; i > 0; i--)
	{
		if (temp[count] != i)
		{
			dfs(adj, i);
		}
		else
		{
			count++;
		}
	}

	//Print the resulting stack from dfs
	while (!list.empty())
	{
		cout << s[list.top()] << "\n";
		list.pop();
	}

	return 0;
}


Thanks in advance
Last edited on
I haven't looked at any other code, but dfs() passes its adj vector by value. That is, each recursive call makes a copy of the entire vector.
Last edited on
Topic archived. No new replies allowed.