All Tracks Algorithms Graphs Graph Representation Problem

The Graph Permutation
Tag(s):

Algorithms, Easy, Graph Representation, Graphs, approximate, homomorphism

Problem
Editorial
Analytics

You are given an undirected graph $$G$$ of $$N$$ vertices and $$M$$ edges. Additionally, you are given a set of $$K$$ edges. Your goal is to generate a permutation $$P$$ of $$N$$ integers such that if each node $$i$$ in the original graph is replaced by node $$P[i]$$ then the count of edges which belong to the set of $$K$$ edges and exist in the new graph as a cycle-edge should be maximized. An edge is a cycle-edge if it belongs to any cycle in the graph.

Input
The first line contains two space-separated integers $$N$$ and $$M$$. Next $$M$$ lines contain a pair of integers $$(u,v)$$ which denote that there is an edge between the two nodes in $$u$$ and $$v$$. Next line contains an integer $$K$$ which denotes count of edges in the new set. Now next $$K$$ lines each contain two space-separated integers $$u$$ and $$v$$ which denote the edge between node $$u$$ and $$v$$. 
There are no multiple edges or self-loop in the graph.

Output
In the output, you need to print a permutation of first $$N$$ natural numbers (space-separated) that optimize the criteria in the statement above.

Constraints
$$1 \le N \le 10^5$$
$$1 \le M , K \le 2 \times 10^5$$
$$1 \le u , v \le N$$

Scoring
If $$X$$ count of edges out of $$K$$ satisfy the condition above then your score is given by $$X / K$$. Your solution will be considered better if you have more score.

Verdict
The output should contain exactly $$N$$ distinct natural numbers in the range $$[1 , N]$$. If your output meets the required format, you will be awarded an AC verdict with a score. In all other cases, you will receive either WA or RE.

SAMPLE INPUT
5 5
1 2
1 3
3 4
3 5
4 5
5
1 2
1 3
3 4
4 5
3 5
SAMPLE OUTPUT
1 2 3 4 5
Explanation

In the sample output, the permutation is 1 2 3 4 5 so it means that the new graph is similar to the old graph. There are 3 edges out of 5 in the new graph that belong to the cycle. So your score for this output is $$3/5 = 0.6$$. There may be other scores possible too with different permutations.

Time Limit: 3.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: Bash, C, C++, C++14, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), TypeScript, Julia, Kotlin, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Swift, Swift-4.1, Visual Basic

CODE EDITOR

Initializing Code Editor...
Your Rating:

Contributor

This Problem was Asked in

NetApp

Challenge Name

CodeNet 2018

OTHER PROBLEMS OF THIS CHALLENGE
Notifications
View All Notifications

?