Generating Cycles CodeChef Solution – Queslers

Problem: Generating Cycles CodeChef Solution

A vertex-induced subgraph of a simple graph GG is one that can be obtained from GG by removing some (possibly, none) vertices. When a vertex is removed, all edges incident to it must also be removed.

A vertex-induced cycle is a vertex-induced subgraph that is also a cycle.

Equivalently, a cycle CC is vertex induced, if for every edge ee in the graph GG that does not belong to CC, at most one of its ends lies on CC.

You are given a simple undirected graph GG with NN vertices and MM edges. Each edge has a label that is either 00 or 11.

In one move, you can select any vertex-induced cycle in GG and flip the values of the label in all edges of the cycle, (i.e. change every 00 to a 11 and every 11 to a 00). The cost of one such move is equal to the size (i.e. number of edges) of the cycle. The total cost for a sequence of moves is the sum of the costs of each individual move.

Determine if there exists a sequence of moves after which all edges have label 00. If such a sequence exists, then find a sequence of moves whose total cost does not exceed 3⋅k3⋅k, where kk is the number of edges in GG that have label 11 before any moves are done; otherwise, print −1−1.

It’s guaranteed that if an answer exists, there exists a sequence of moves with a total cost not exceeding 3⋅k3⋅k.

Note: Test data contains large input files. It is recommended that you use fast input/output methods.

Input Format

• The first line of input contains an integer TT, the number of test cases. The description of the TT test cases follows.
• The first line of each test case contains two space-separated integers N,MN,M — the number of vertices and edges of the graph respectively.
• The next MM lines of each test case contain three space-separated integers u,vu,v, and ww, denoting an edge between vertices u,vu,v with label ww.

Output Format

• For each test case, print the answer starting from a new line in the following format:
• If it is impossible to convert all edge labels to 00 as per the statement, then print −1−1.
• Otherwise, in the first line print the number of operations that you require to perform, (say xx).
• In the ii-th of the next xx lines, print the number of vertices of the cycle you choose in the ii-th move followed by the vertices of the cycle. The vertices must be printed in either clockwise or anticlockwise order. That is, print s x1 x2 … xss x1 x2 … xs to denote a cycle of size ss whose edges are (x1,x2),(x2,x3),…,(xs−1,xs),(xs,x1)(x1,x2),(x2,x3),…,(xs−1,xs),(xs,x1).
• If there are multiple correct outputs, you may print any of them.

Constraints

• 1≤T≤1031≤T≤103
• 1≤N≤1031≤N≤103
• 1≤M≤N(N−1)21≤M≤N(N−1)2
• The sum of NN over all test cases does not exceed 20002000
• The sum of kk over all test cases does not exceed 50005000
• 1≤u,v≤n1≤u,v≤n
• The given graph is a simple graph, i.e. there are no self loops or multiple edges

Subtasks

Subtask 1 (100 pts): Original constraints

Sample Input 1 

4
6 9
1 2 1
2 3 1
3 4 1
4 5 1
5 6 1
6 1 1
1 3 1
3 5 1
5 1 1
6 9
1 2 1
2 3 1
3 4 1
4 5 1
5 6 1
6 1 1
1 3 0
3 5 0
5 1 0
2 1
1 2 0
2 1
1 2 1

Sample Output 1 

5
3 3 4 5 
3 1 2 3 
3 1 3 5 
3 1 5 6 
3 1 3 5 
4
3 3 4 5 
3 1 2 3 
3 1 3 5 
3 1 5 6 
0
-1

Explanation

Test Case 1: In this example N=6,M=9N=6,M=9 and k=9k=9. The total cost of the sequence of moves given is 1515. The graph and the sequence of moves are shown below.

Note that any solution for which the total cost is no more than 3⋅k=273⋅k=27 is also considered correct. For example another solution is shown below with total cost equal to 99.

Test Case 2: The graph is same as the previous testcase, except that the edge labels are different (k=6k=6). After the first move, the resulting graph is identical to the first case. The total cost is 1212 which is less than 3⋅k=183⋅k=18. The solution for this case is shown below.

Note that the cycle formed by vertices 1,2,3,4,5,61,2,3,4,5,6 is not a vertex induced cycle.

Test Case 3: The graph does not have any edge with label 11, so no operations are required.

Test Case 4: The graph does not contain any cycles, and therefore it is impossible to flip the label of any edge (i.e. no valid move exists).

Generating Cycles CodeChef Solution in C++

#include<iostream>
#include<cstdio>
#include<cstring>
#include<bitset>
#include<vector>
#define N 1010
using namespace std;
bitset<N>f[N],mp[N];
bool in[N];
int ton[N],deg[N],tp;
vector<vector<int>>cir;
int n,m;
void dfs(int u)
{
    ton[++tp]=u;in[u]=true;
    for(int i=tp-2;i>0;i--)
    {
        int v=ton[i];
        if(!mp[u][v]) continue;
        vector<int>res;res.reserve(tp-i+1);
        for(;ton[tp]!=v;tp--)
        {
            f[ton[tp-1]][ton[tp]]=f[ton[tp]][ton[tp-1]]=0;
            res.push_back(ton[tp]);
            in[ton[tp]]=false;
        }
        res.push_back(v);
        cir.push_back(res);
        if(f[u][v]){f[u][v]=f[v][u]=0;return;}
        f[u][v]=f[v][u]=1;
        ton[++tp]=u;in[u]=true;
        i=tp-1;
    }
    for(int v=f[u]._Find_first();v<=n;v=f[u]._Find_next(v)) if(!in[v])
    {
        dfs(v);
        if(!in[u]) return;
    }
    tp--;in[u]=false;
}
void solve()
{
    for(int i=1;i<=n;i++) deg[i]=0;
    for(int i=1;i<=n;i++) mp[i].reset(),f[i].reset();
    cir.clear();
    scanf("%d%d",&n,&m);
    for(int i=1,x,y,z;i<=m;i++)
    {
        scanf("%d%d%d",&x,&y,&z);
        mp[x][y]=mp[y][x]=true;
        if(z) f[x][y]=f[y][x]=true,deg[x]++,deg[y]++;
    }
    for(int i=1;i<=n;i++) if(deg[i]&1){puts("-1");return;}
    for(int i=1;i<=n;i++) if(f[i].any()) dfs(i);
    printf("%d\n",(int)cir.size());
    for(auto u:cir)
    {
        printf("%d ",(int)u.size());
        for(int v:u) printf("%d ",v);
        puts("");
    }
}
int main()
{
    int t;
    scanf("%d",&t);
    while(t --> 0) solve();
    return 0;
}

Generating Cycles CodeChef Solution in Java

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

class Codechef 
{
	static class Edge 
	{
		int v, w, u;
		int globalID;
		public Edge(int v, int u) 
		{
			this.v = v; this.u = u;
		}
		public Edge(int v, int w, int globalID) 
		{
			this.v = v; this.w = w; this.globalID = globalID;
		}
	}
	static boolean[] edgeVisited;
	static boolean dfs(int currentVertex, int startVertex, boolean[] vertexVisited, ArrayList<Integer> cycle) 
	{
		if(currentVertex == startVertex)
			return true;
		if(vertexVisited[currentVertex])
			return false;
		vertexVisited[currentVertex] = true;
		for(Edge e : adjOne.get(currentVertex)) 
		{
			if(edgeVisited[e.w])
				continue;
			if(dfs(e.v, startVertex, vertexVisited, cycle)) 
			{
				cycle.add(currentVertex);
				edgeVisited[e.w] = true;
				return true;
			}
		}
		return false;
	}
	static ArrayList<ArrayList<Integer>> moves;
	static int[] cycleID;
	static int forwardDistance(int a, int b, int cycleLength) 
	{		
		if(b >= a)
			return b - a;
		return cycleLength - (a-b);
	}
	static boolean[] vertexDone;
	static void traverseCycles(int currentVertex, int startVertex, int[] cycleID, boolean[] globalEdgeVisited, ArrayList<Integer> move, int cycleLength) 
	{
		if(currentVertex == startVertex) 
		{
			moves.add(move);
			return;
		}
		if(vertexDone[cycleID[currentVertex]])
			return;
		vertexDone[cycleID[currentVertex]] = true;
		move.add(currentVertex);
		ArrayList<Edge> nextSteps = new ArrayList<Edge>();
		for(Edge e : adj.get(currentVertex)) 
		{
			if(globalEdgeVisited[e.globalID] || cycleID[e.v] == -1
					|| forwardDistance(cycleID[currentVertex],cycleID[e.v],cycleLength) > forwardDistance(cycleID[currentVertex],cycleID[startVertex],cycleLength)) {
				continue;
			}
			nextSteps.add(e);
		}
		Collections.sort(nextSteps, new Comparator<Edge>() 
		{
			@Override
			public int compare(Edge arg0, Edge arg1) 
			{
				return forwardDistance(cycleID[currentVertex],cycleID[arg0.v],cycleLength) - forwardDistance(cycleID[currentVertex],cycleID[arg1.v],cycleLength);
			}
		});
		int nextStepsSize = nextSteps.size();
		for(int A = 0; A < nextStepsSize-1; A++) 
		{
			Edge topEdge = nextSteps.get(A);
			ArrayList<Integer> newMove = new ArrayList<Integer>();
			newMove.add(nextSteps.get(A+1).v);
			newMove.add(currentVertex);
			globalEdgeVisited[topEdge.globalID] = true;
			traverseCycles(topEdge.v, nextSteps.get(A+1).v, cycleID, globalEdgeVisited, newMove, cycleLength);
		}
		globalEdgeVisited[nextSteps.get(nextStepsSize-1).globalID] = true;
		traverseCycles(nextSteps.get(nextStepsSize-1).v,startVertex, cycleID, globalEdgeVisited, move, cycleLength);
	}
	static ArrayList<ArrayList<Edge>> adj;
	static ArrayList<ArrayList<Edge>> adjOne;
	public static void main(String[] args) throws IOException 
	{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		PrintWriter pw = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int t = Integer.parseInt(st.nextToken());
		for(int testCase = 0; testCase < t; testCase++) 
		{
			st = new StringTokenizer(br.readLine());
			int n = Integer.parseInt(st.nextToken());
			int m = Integer.parseInt(st.nextToken());
			adj = new ArrayList<ArrayList<Edge>>();
			adjOne = new ArrayList<ArrayList<Edge>>();
			for(int A = 0; A < n; A++) 
			{
				adj.add(new ArrayList<Edge>());
				adjOne.add(new ArrayList<Edge>());
			}
			int weightOneID = 0;
			int globalID = 0;
			int[][] globalIDFromNodes = new int[n][n];
			ArrayList<Edge> inverseOneID = new ArrayList<Edge>();
			for(int A = 0; A < m; A++) 
			{
				st = new StringTokenizer(br.readLine());
				int v = Integer.parseInt(st.nextToken())-1;
				int u = Integer.parseInt(st.nextToken())-1;
				int w = Integer.parseInt(st.nextToken());
				globalIDFromNodes[v][u] = globalID;
				globalIDFromNodes[u][v] = globalID;
				if(w == 1) 
				{
					adjOne.get(v).add(new Edge(u,weightOneID, globalID));
					adjOne.get(u).add(new Edge(v,weightOneID, globalID));
					adj.get(v).add(new Edge(u,w, globalID));
					adj.get(u).add(new Edge(v,w, globalID));
					inverseOneID.add(new Edge(v,u));
					weightOneID++;
					globalID++;
				} 
				else 
				{
					adj.get(v).add(new Edge(u,w,globalID));
					adj.get(u).add(new Edge(v,w,globalID));
					globalID++;
				}
			}
			boolean possible = true;
			
			if(!possible) 
			{
				pw.println(-1);
				continue;
			}
			ArrayList<ArrayList<Integer>> cycles = new ArrayList<ArrayList<Integer>>();
			int k = weightOneID;
			edgeVisited = new boolean[k];
			int edgesLeft = k;
			for(int A = 0; A < k; A++) 
			{
				if(edgeVisited[A])
					continue;
				edgeVisited[A] = true;
				ArrayList<Integer> cycle = new ArrayList<Integer>();
				boolean[] visited = new boolean[n];
				if(dfs(inverseOneID.get(A).u, inverseOneID.get(A).v, visited, cycle)) 
				{
					cycle.add(inverseOneID.get(A).v);
					cycles.add(cycle);
				} 
				else 
				{
					possible = false;
					break;
				}
			}
			if(!possible) 
			{
				pw.println(-1);
				continue;
			}
			moves = new ArrayList<ArrayList<Integer>>();
			cycleID = new int[n];
			Arrays.fill(cycleID, -1);
			for(ArrayList<Integer> cycle : cycles) 
			{
				int cycleLength = cycle.size();
				vertexDone = new boolean[cycleLength];
				for(int A = 0; A < cycleLength; A++)
					cycleID[cycle.get(A)] = A;
				boolean[] globalEdgeVisited = new boolean[m];
				globalEdgeVisited[globalIDFromNodes[cycle.get(0)][cycle.get(1)]] = true;
				ArrayList<Integer> firstMove = new ArrayList<Integer>();
				firstMove.add(cycle.get(0));
				traverseCycles(cycle.get(1), cycle.get(0), cycleID, globalEdgeVisited, firstMove, cycleLength);
				for(int A = 0; A < cycleLength; A++)
					cycleID[cycle.get(A)] = -1;
			}
			pw.println(moves.size());
			for(ArrayList<Integer> move : moves) 
			{
				int cycleLength = move.size();
				pw.print(cycleLength + " ");
				for(int A = 0; A < cycleLength-1; A++) 
				{
					pw.print((move.get(A)+1) + " ");
				}
				pw.print(move.get(cycleLength-1)+1);
				pw.println();
			}
		}
		pw.close();
	}
}

Generating Cycles CodeChef Solution Review:

In our experience, we suggest you solve this Generating Cycles CodeChef Solution and gain some new skills from Professionals completely free and we assure you will be worth it.

Generating Cycles Problem is available on Hacker Rank for Free, if you are stuck anywhere between a compilation, just visit Queslers to get Generating Cycles CodeChef Solution.

Conclusion:

I hope this Generating Cycles CodeChef Solution would be useful for you to learn something new from this problem. If it helped you then don’t forget to bookmark our site for more Hacker Rank, Leetcode, Codechef, Codeforce Solution.

This Problem is intended for audiences of all experiences who are interested in learning about Data Science in a business context; there are no prerequisites.

Keep Learning!

More CodeChef Solutions >>

Olympics Ranking CodeChef Solution

Problem Difficulties CodeChef Solution

Chef and Bulb Invention CodeChef Solution

Array Filling CodeChef Solution

Special Triplets CodeChef Solution