Physical Address
304 North Cardinal St.
Dorchester Center, MA 02124
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.
Subtask 1 (100 pts): Original constraints
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
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
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).
#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;
}
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();
}
}
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.
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