[백준] 2252번: 줄 세우기

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

initial

I had to look at topological sort algorithm but this question is a typical example of such sort.

Topological sorting is used in this context because it allows us to determine the correct order in which students should be arranged in a line based on the partial information about their heights and comparisons between some of the students.

In this problem, you are given a set of height comparisons between pairs of students. Each comparison gives us a relationship like "Student A is taller than Student B" or "Student A is shorter than Student B." These relationships can be represented as directed edges in a graph, where each student is a vertex, and the direction of the edge indicates the height relationship.

For example, if you have the comparisons:

1. Student A is taller than Student B.
2. Student B is shorter than Student C.

You can represent these relationships as:

A -> B -> C

This forms a directed acyclic graph (DAG) where arrows point from shorter students to taller students. The topological sorting of this DAG will give us a valid linear order in which students can be arranged in a line while respecting the height relationships.

Here's how the process works:

1. Build a directed graph where each vertex represents a student, and there is an edge from Student A to Student B if Student A is taller than Student B.

2. Perform a topological sort on this graph. The result of the topological sort will give us an ordering of students where taller students appear before shorter ones, and it respects all the given height comparisons.

3. The ordered list obtained from the topological sort represents the valid arrangement of students in a line based on the provided height comparisons.

In summary, topological sorting is used here because it helps us find a valid linear order of students based on partial height comparisons, ensuring that the height relationships are consistent and there are no cycles, which would indicate contradictory comparisons.

so my correct solution:

from collections import deque

n, k = map(int, input().split())
indegree = [0 for _ in range(n+1)]
graph =[[] for _ in range(n+1)]
for _ in range(k):
    a,b = map(int, input().split())
    graph[a].append(b)
    indegree[b]+=1

def topology_sort():
    result = []
    queue=deque()
    for i in range(1,n+1):
        if indegree[i]==0:
            queue.append(i)
    while queue:
        cur = queue.popleft()
        result.append(cur)
        for i in graph[cur]:
            indegree[i]-=1
            if indegree[i]==0:
                queue.append(i)
    for i in result:
        print(i, end = ' ')
topology_sort()

revisited feb 27th

yep more or less pasting the topo sort template but need to know when to use this algorithm. It is used to find reachabilitiy of a certain node or an order of nodes to be traversed.

complexity

The provided code performs topological sorting on a directed graph to find a valid linear order of elements. Here's the complexity analysis of the code:

1. Input Reading (Linear Time):

   • Reading n and k takes constant time.
   • The loop for reading k pairs of values (a and b) takes linear time in terms of k, O(k).

2. Graph Initialization (Constant Time):

   • Initializing indegree and graph arrays takes constant time based on n.

3. Building the Graph (Linear Time):

   • The loop that processes k pairs and populates the graph and indegree arrays takes linear time in terms of k, O(k). It creates directed edges in the graph based on the input pairs.

4. Topological Sorting (Linear Time):

   • The topology_sort function performs topological sorting using a queue. In the worst case, it processes all vertices, which is n. For each vertex, it examines its neighbors and updates the indegree count.
   • The while loop in the topology_sort function runs in O(n) time since it processes each vertex once.

5. Printing the Result (Linear Time):

   • The loop for printing the result runs in O(n) time since it iterates through the result list.

Overall, the time complexity of the code is dominated by the topological sorting process, which is O(n) because it processes each vertex once. The other operations, such as input reading and graph initialization, do not significantly affect the overall time complexity.

The space complexity of the code is O(n) because it uses data structures (arrays and a queue) that grow with the number of vertices.