Generating Cycles GENECYC Solution Codechef

Codechef Generating Cycles GENECYC 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.

JJqptiM.gif

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.

onyz3pU.gif

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.

JqEMJSL.gif

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).

January Long Challenge 2022
January Long Challenge 2022

Solution

Program: Generating Cycles GENECYC 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;
}

Program: Generating Cycles GENECYC Solution in Java

Program: Generating Cycles GENECYC Solution in Python

January Long Challenge 2022 Solution

December Long Challenge 2021 Solution

Leave a Comment