Generate Permutation by Swaps

Generate Permutation by Swaps

Hard PHP PHP Functions 29 views
Explanation Complexity

Problem Statement

Given n and a list of swaps (i j), start with [1..n]. Apply swaps and print the final array.

Input Format

First line n q. Next q lines i j (1-based).

Output Format

One line n integers.

Example

5 3
1 5
2 4
3 4
5 4 2 3 1

Constraints

n,q

Input / Output Format

Input Format
First line n q. Next q lines i j (1-based).
Output Format
One line n integers.
Constraints
n,q

Examples

Input:
5 3 1 5 2 4 3 4
Output:
5 4 2 3 1

Example Solution (Public)

PHP 
<?php
$inputText=rtrim(stream_get_contents(STDIN));
if($inputText==='') exit;
$inputLines=preg_split('/\\R/', $inputText);
$first=preg_split('/\\s+/', trim($inputLines[0] ?? ''));
$n=intval($first[0] ?? 0);
$q=intval($first[1] ?? 0);
$a=[];
for($i=1;$i<=$n;$i++) $a[]=$i;
for($k=0;$k<$q;$k++){
  $tokens=preg_split('/\\s+/', trim($inputLines[$k+1] ?? ''));
  $i=intval($tokens[0] ?? 1)-1;
  $j=intval($tokens[1] ?? 1)-1;
  $tmp=$a[$i]; $a[$i]=$a[$j]; $a[$j]=$tmp;
}
echo implode(' ',array_map('strval',$a));
?>

Official Solution Code

<?php
$inputText=rtrim(stream_get_contents(STDIN));
if($inputText==='') exit;
$inputLines=preg_split('/\\R/', $inputText);
$first=preg_split('/\\s+/', trim($inputLines[0] ?? ''));
$n=intval($first[0] ?? 0);
$q=intval($first[1] ?? 0);
$a=[];
for($i=1;$i<=$n;$i++) $a[]=$i;
for($k=0;$k<$q;$k++){
  $tokens=preg_split('/\\s+/', trim($inputLines[$k+1] ?? ''));
  $i=intval($tokens[0] ?? 1)-1;
  $j=intval($tokens[1] ?? 1)-1;
  $tmp=$a[$i]; $a[$i]=$a[$j]; $a[$j]=$tmp;
}
echo implode(' ',array_map('strval',$a));
?>
Please login to submit solutions.
Editor
Output

                                        

                                    

                                    

                                        

                                                                                    
Please login to submit solutions.