CAPCITY SPOJ.com solution C++

Problem : spoj.com/problems/CAPCITY

Algorithm : Kosaraju's Algorithm ( Two pass, Strongly connected components, kernel dag )

Source: (C++ : AC)

#include <stdio.h>
#include <vector>
#include <algorithm>

using namespace std;

int V, E;
vector<vector<int> > G;
vector<vector<int> > GD;
vector<vector<int> > res;
vector<vector<int> > SCCconn;

vector<int> sortOrder;

bool *marked;
int *reg;
int groupNo;

void dfs(int vertex){
 if(marked[vertex])return;
 marked[vertex] = true;
 
 for(int i=0;i<G[vertex].size();++i) dfs(G[vertex][i]);
 sortOrder.push_back(vertex);
}

void dfs2(int vertex){
 if(marked[vertex])return;
 marked[vertex] = true;
 
    for(int i=0;i<GD[vertex].size();++i)dfs2(GD[vertex][i]);
 res[groupNo].push_back(vertex); 
 reg[vertex] = groupNo;
}

void dfs3(int callingGroup, int vertex){
 if(marked[vertex]){
  if(callingGroup!=reg[vertex])SCCconn[callingGroup].push_back(reg[vertex]);
  return;
 }
  marked[vertex] = true;
  for(int i=0;i<GD[vertex].size();++i){
   dfs3(callingGroup, GD[vertex][i]);
  }
}

int dfs4(int callingGroup){
 int size=0;
 for(int i=0;i<SCCconn[callingGroup].size();++i){
  size+=dfs4(SCCconn[callingGroup][i]);
 }
 size+=res[callingGroup].size();
 return size;
}

int main(){
 scanf("%d %d", &V, &E);
 marked = new bool[V];
 reg = new int[V];
 
 for(int i=0;i<V;++i)marked[i] = false;
 for(int i=0;i<V;++i)reg[i] = -1;
 groupNo = -1;
 
 for(int i=0;i<V;++i){
  vector<int> x,xx,xxx,xxxx;
  res.push_back(x);
  G.push_back(xx);
  GD.push_back(xxx);
  SCCconn.push_back(xxxx);
 }
 
 for(int i=0;i<E;++i){
  int from, to;
  scanf("%d %d", &from, &to);
  from--;to--;
  G[from].push_back(to);
  GD[to].push_back(from);
 }
 
 if(V==1){
  printf("%d\n%d", 1, V);
  return 0;
 }
 for(int i=0;i<V;++i)dfs(i);
 for(int i=0;i<V;++i)marked[i] = false;
  for(int i=sortOrder.size()-1;i>=0;--i){ 
   if(!marked[sortOrder[i]])groupNo++;
   dfs2(sortOrder[i]);
 } 
 vector<int> result;
 for(int i=0;i<V;++i)marked[i] = false;
 for(int i=0;i<V;++i){
  if(res[i].size()==0)break;
  for(int j=0;j<res[i].size();++j){
   dfs3(i, res[i][j]);
  }
 }
 
 for(int i=0;i<SCCconn.size();++i){
  int sizeOfGroup = dfs4(i); 
  if(sizeOfGroup==V){
   for(int j=0;j<res[i].size();++j){
    result.push_back(res[i][j]);
   }
  }
 }
 printf("%d\n", result.size());
 sort(result.begin(), result.end());
  
 for(int i=0;i<result.size();++i)printf("%d ", result[i]+1);
 printf("\n");
}

SPOJ BOTTOM Solution : Strongly Connected Components : Kosaraju's Algorithm

Problem : http://www.spoj.com/problems/BOTTOM/

Source: C++ AC (0.02s):

#include <stdio.h>
#include <vector>
#include <algorithm>

using namespace std;

int V, E;
vector<vector<int> > G;
vector<vector<int> > GD;
vector<vector<int> > res;

vector<int> sortOrder;

bool *marked;
int *reg;
int groupNo;

void dfs(int vertex){
 if(marked[vertex])return;
 marked[vertex] = true;
 
 for(int i=0;i<G[vertex].size();++i) dfs(G[vertex][i]);
 sortOrder.push_back(vertex);
}

void dfs2(int vertex){
 if(marked[vertex])return;
 marked[vertex] = true;
 
    for(int i=0;i<GD[vertex].size();++i)dfs2(GD[vertex][i]);
 res[groupNo].push_back(vertex); 
 reg[vertex] = groupNo;
}

int main(){
 while(true){
  scanf(" %d", &V);
  if(V==0)break;
  scanf(" %d", &E);
  
  marked = new bool[V];
  for(int i=0;i<V;++i)marked[i] = false;
  reg = new int[V];
  for(int i=0;i<V;++i)reg[i] = -1;
  
  sortOrder.clear();
  G.clear();
  GD.clear();
  res.clear();
  groupNo = -1;
  
  for(int i=0;i<V;++i){
   vector<int> t,tt,ttt;
   res.push_back(t);
   G.push_back(tt);
   GD.push_back(ttt);
  }
  
  if(E!=0){ 
   for(int j=0;j<E;++j){
    int from, to;
    scanf(" %d %d", &from, &to); 
    from--;
    to--;
    G[from].push_back(to);
    GD[to].push_back(from);
   } 
  }
  for(int i=0;i<V;++i)dfs(i);
  for(int i=0;i<V;++i)marked[i] = false;
  for(int i=sortOrder.size()-1;i>=0;--i){ 
   if(!marked[sortOrder[i]])groupNo++;
   dfs2(sortOrder[i]);
  } 
  
  vector<int> ans; 
  for(int i=0;i<res.size();++i){ 
   if(res[i].size()>1){
    int group = i;
    bool flag = true; 
    for(int j=0;j<res[i].size();++j){ 
     for(int k=0;k<G[res[group][j]].size();++k){
      if(reg[G[res[group][j]][k]]!=group){
       flag = false;
       break;
      }
     }
     if(!flag)break;
    }
    if(flag){
      for(int j=0;j<res[i].size();++j)ans.push_back(res[i][j]);
    }
   }else if(res[i].size()==1){ 
    if(G[res[i][0]].size()==0)ans.push_back(res[i][0]);
    else if(G[res[i][0]].size()==1 && G[res[i][0]][0]==res[i][0])ans.push_back(res[i][0]);
   } 
  }
  std::sort(ans.begin(), ans.end());   
  for(int i=0;i<ans.size();++i){
   printf("%d ", ans[i]+1); 
  }
  printf("\n");
 }
}

Strongly Connected Components : Kosaraju’s algorithm Implementation - Java

Helpful links for algorithm exaplanation :

http://www.geeksforgeeks.org/strongly-connected-components/

Source:

import java.io.*;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;

public class KosarajuSharirStronglyConnectedComponents {
    static int V, E;
    static ArrayList<ArrayList<Integer>> G = new ArrayList<>(); 
    static ArrayList<ArrayList<Integer>> GD = new ArrayList<>(); 
    
    static ArrayList<Integer> sortOrder = new ArrayList<>();
    
    static boolean marked[];
    static int reg[];
    static int groupNo=0;
    
    static void dfs(int vertex){
        if(marked[vertex])return;
        
        marked[vertex] = true;
        
        for(int c:G.get(vertex)){
            dfs(c);
        } 
        sortOrder.add(vertex);
    }
    
    static void dfs2(int vertex){
        if(marked[vertex])return;
        
        marked[vertex] = true;
        
        for(int c:GD.get(vertex)){
            dfs2(c); 
        }
        reg[vertex] = groupNo;
    }
    
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new FileReader("e:\\inputVideo.txt"));
        String s = null;
        
        V = Integer.parseInt(br.readLine());
        E = Integer.parseInt(br.readLine());
        
        marked = new boolean[V];
        reg = new int[V];
        
        for(int i=0;i<V;++i){G.add(new ArrayList<>());GD.add(new ArrayList<>());}
        
        while((s=br.readLine())!=null){
            String d[] = s.split(" ");
            int from, to;
            from = Integer.parseInt(d[0]);
            to = Integer.parseInt(d[1]);
            
            G.get(from).add(to);
            GD.get(to).add(from);
        }
        
        for(int i=0;i<V;++i){
            dfs(i);
        }
        
        System.out.println(sortOrder); 
        Collections.reverse(sortOrder);
        
        Arrays.fill(marked, false); 
        
        for(int i:sortOrder){
            if(!marked[i])groupNo++;
            dfs2(i); 
        }
        
        for(int i=0;i<reg.length;++i){
            System.out.println("Node "+i+" group = "+reg[i]);
        }
    } 
}

Input Format:

Number of vertices V

Number of edges     E

Directed edges Node-from to Node-to

.

.

.

Eth edge

Input File (2 tests):

File #1 Contents:

13

20

0 1

0 5

2 0

2 3

3 2

3 5

4 2

6 0

6 8

6 4

6 9

7 6

7 9

8 6

9 10

9 11

10 12

11 12

11 4

12 9

File #2 Contents (Example case geeksforgeeks):

5

5

1 0

0 2

2 1

0 3

3 4

Output:

For Test #1:

[1, 2, 4, 3, 0]

Node 0 group = 1

Node 1 group = 1

Node 2 group = 1

Node 3 group = 2

Node 4 group = 3

For Test #2:

[1, 5, 0, 3, 2, 4, 8, 12, 10, 11, 9, 6, 7]

Node 0 group = 6

Node 1 group = 8

Node 2 group = 5

Node 3 group = 5

Node 4 group = 4

Node 5 group = 7

Node 6 group = 2

Node 7 group = 1

Node 8 group = 2

Node 9 group = 3

Node 10 group = 3

Node 11 group = 3

Node 12 group = 3

Practice problems: SPOJ: http://www.spoj.com/problems/WEBISL/

Solution :Java: AC:

import java.io.*;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;

class WEBISL {
    static int V, E;
    static ArrayList<ArrayList<Integer>> G = new ArrayList<>(); 
    static ArrayList<ArrayList<Integer>> GD = new ArrayList<>(); 
    
    static ArrayList<Integer> sortOrder = new ArrayList<>();
    
    static boolean marked[];
    static int reg[];
    static int groupNo=-1;
    
    static void dfs(int vertex){
        if(marked[vertex])return;
        
        marked[vertex] = true;
        
        for(int c:G.get(vertex)){
            dfs(c);
        } 
        sortOrder.add(vertex);
    }
    static int[] groups;
    static void dfs2(int vertex){
        if(marked[vertex])return;
        
        marked[vertex] = true;
        
        for(int c:GD.get(vertex)){
            dfs2(c); 
        }
        if(groups[groupNo]>vertex)groups[groupNo]=vertex;
        reg[vertex] = groupNo;
    }
    
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String s = null;
        
        String[] fD = br.readLine().split(" ");
        V = Integer.parseInt(fD[0]);
        E = Integer.parseInt(fD[1]);
        groups = new int[V];
        Arrays.fill(groups, Integer.MAX_VALUE);
        marked = new boolean[V];
        reg = new int[V];
        
        for(int i=0;i<V;++i){G.add(new ArrayList<>());GD.add(new ArrayList<>());}
        
        while(E-->0){
            s = br.readLine();
            String d[] = s.split(" ");
            int from, to;
            from = Integer.parseInt(d[0]);
            to = Integer.parseInt(d[1]);
            
            G.get(from).add(to);
            GD.get(to).add(from);
        }
        
        for(int i=0;i<V;++i){
            dfs(i);
        }
        
//        System.out.println(sortOrder); 
        Collections.reverse(sortOrder);
        
        Arrays.fill(marked, false); 
        
        for(int i:sortOrder){
            if(!marked[i]){groupNo++;}
            dfs2(i); 
        }
         
        for(int i=0;i<reg.length;++i){
            System.out.println(groups[reg[i]]);
        }
//        System.out.println(Arrays.toString(groups));
//        System.out.println(Arrays.toString(reg));
    } 
}

ROCK. SPOJ - ROCK solution

Problem: www.spoj.com/problems/ROCK


Source (Java), AC:

import java.io.*;

class ROCK {

    public static int[] data;
    public static int[][] dp;

    public static int solve(int from, int to) {
        int ones = 0, zeros = 0;
        
        if(from>to)return 0;
        if (dp[from][to] != -1) return dp[from][to]; 
        
        for (int i = from; i <= to; ++i) {
            if (data[i] == 1) ones++;
            else zeros++;
        }
        
        if(ones>zeros)return dp[from][to]=ones+zeros;
         
        if(from==to) return data[to];
        int max = 0;
         
        for(int i=from;i<=to;++i){  
            int left = 0;
            if(i!=to)left = solve(from, i); 
            int right = 0;
            if(i+1!=from)right = solve(i+1, to); 
            if(left+right>max){max = left+right;}
        } 
        return dp[from][to] = max;
    }

    public static void main(String[] args) throws Exception {
        int nCases = IO.nextInt();
        while (nCases-- > 0) {
            int length = IO.nextInt();
            data = IO.nextIntArray(length, "");
            dp = new int[length + 1][length + 1];
            for (int i = 0; i < length + 1; ++i) {
                for (int j = 0; j < length + 1; ++j) {
                    dp[i][j] = -1;
                }
            }
            IO.println(solve(1, length));
        }
    }

    static class IO {

        static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        public static int[][] next2dInt(int rows, int cols, String seperator) throws Exception {
            int[][] arr = new int[rows + 1][cols + 1];
            for (int i = 1; i <= rows; ++i) {
                arr[i] = nextIntArray(cols, seperator);
            }
            return arr;
        }

        public static int[] nextIntArray(int nInts, String seperator) throws IOException {
            String ints = br.readLine();
            String[] sArray = ints.split(seperator);
            int[] array = new int[nInts + 1];
            for (int i = 1; i <= nInts; ++i) {
                array[i] = Integer.parseInt(sArray[i - 1]);
            }
            return array;
        }

        public static long[] nextLongArray(int nLongs, String seperator) throws IOException {
            String longs = br.readLine();
            String[] sArray = longs.split(seperator);
            long[] array = new long[nLongs + 1];
            for (int i = 1; i <= nLongs; ++i) {
                array[i] = Long.parseLong(sArray[i - 1]);
            }
            return array;
        }

        public static double[] nextDoubleArray(int nDoubles, String seperator) throws IOException {
            String doubles = br.readLine();
            String[] sArray = doubles.split(seperator);
            double[] array = new double[nDoubles + 1];
            for (int i = 1; i <= nDoubles; ++i) {
                array[i] = Double.parseDouble(sArray[i - 1]);
            }
            return array;
        }

        public static char[] nextCharArray(int nChars, String seperator) throws IOException {
            String chars = br.readLine();
            String[] sArray = chars.split(seperator);
            char[] array = new char[nChars + 1];
            for (int i = 1; i <= nChars; ++i) {
                array[i] = sArray[i - 1].charAt(0);
            }
            return array;
        }

        public static int nextInt() throws IOException {
            String in = br.readLine();
            return Integer.parseInt(in);
        }

        public static double nextDouble() throws IOException {
            String in = br.readLine();
            return Double.parseDouble(in);
        }

        public static long nextLong() throws IOException {
            String in = br.readLine();
            return Long.parseLong(in);
        }

        public static int nextChar() throws IOException {
            String in = br.readLine();
            return in.charAt(0);
        }

        public static String nextString() throws IOException {
            return br.readLine();
        }

        public static void print(Object... o) {
            for (Object os : o) {
                System.out.print(os);
            }
        }

        public static void println(Object... o) {
            for (Object os : o) {
                System.out.print(os);
            }
            System.out.print("\n");
        }

        public static void printlnSeperate(String seperator, Object... o) {
            StringBuilder sb = new StringBuilder();
            sb.delete(sb.length() - seperator.length(), sb.length());
            System.out.println(sb);
        }
    }
}

WORDS1 SPOJ.com Euler Path. Graph Theory.

Problem : http://www.spoj.com/problems/WORDS1/

These links are helpful:

http://en.wikipedia.org/wiki/Eulerian_path

https://www.youtube.com/watch?v=REfC1-igKHQ

https://www.youtube.com/watch?v=5M-m62qTR-s

http://www.quora.com/How-do-I-solve-the-SPOJ-Play-on-Words-problem

http://web.iiit.ac.in/~mayank.natani/SPOJ/WORDS1.cpp

My JAVA solution (Accepted):

import java.io.*;
import java.math.*;
import java.util.*;

public class WORDS1Attempt2 {

    
    public static boolean checkConnections(int index) { 
        /*
        If broken connections equal total number of connections, we are done, the graph is connected.
        */
        if(broken == connections)return true;
        int row = index;
         
        for(int i=1;i<27;++i){
            /*
            either this vertex can reach some other vertex or some other vertex can reach this vertex. Means they are connected.
            */
            if(graph[row][i]||graph[i][row]){ 
                if(graph[row][i])broken++;
                graph[row][i] = false; 
                if(graph[i][row])broken++;
                graph[i][row] = false; 
                if(checkConnections(i))return true; 
            } 
        } 
        //Else if it is not the case, return false.
        return false;
    }

    static boolean[][] graph;
    static int connections = 0;
    static int broken=0;
    
    public static void main(String[] args) throws Exception {
        int nCases = IO.nextInt();
        while (nCases-- > 0) {
            connections=0;
            broken=0;
            graph = new boolean[27][27];
            int[] reg = new int[27];
            int nWords = IO.nextInt();
            int f, s;
            String[] words = new String[nWords];
            
            for (int i = 0; i < nWords; ++i) {
                words[i] = IO.nextString();
                reg[f =(words[i].charAt(0) - 96)]++;
                reg[s =(words[i].charAt(words[i].length() - 1) - 96)]--; 
                
                //Check the number of unique connections in the graph to be later
                //used when checking the graph for connectivity
                if(graph[f][s]==false)connections++; 
                graph[f][s]=true; 
            }
            
            boolean possible = true;
            
            //No of minus one values (-1) in the array reg. this array stores the difference (in-out) connections.
            int mO = 0;
            int pO = 0;  
            //No of zeros in the array reg.
            int zeros=0;
            
            for (int i = 1; i < reg.length; ++i) { 
                if (reg[i] != 0) {
                    if (reg[i] == 1) pO++;
                    else if (reg[i] == -1) mO++;
                    else {
                        possible = false;
                        break;
                    }
                }else zeros++;
            } 
            
            /*
              If in reg array (reg array stores the difference (no of incomming connections - no out outgoing connections)
              number of minus ones (mO) found is 1 and number of plus one found is 1,
              the graph may have an euler path (necessary but not sufficient condition).
              Even if mO and pO equal one, the graph could be a disconnected one for example
              in case 
                abc
                cba

                qcr
                rcx 

              This graph would be disconnected, yet has mO = 1 and pO = 1.
              for this, we need to check if every vertice is 
              connected (no matter the direction of connection) to every other vertice.
            */
            if (!(mO==1 && pO==1)){
                /*
                  If there is no +1 or -1, all the vertices should have out-in connection difference = 0 
                  for the graph to have the possibility of having an euler path.
                */
                if(zeros!=26) possible=false;
            }
            
            if(possible){
                /*
                  The vertex (index in graph) to start the dfs procedure from 
                  This must be the vertex having |in-out connections| value = 1.
                */
                int in=-1;   

                /*
                In case there is no such vertex. (All reg[i] values are 0.
                This means that the graph is of the form
                
                abc
                cbd
                dca
                
                This still has an euler path. The end can be joined to the beginning. (This doesn't bother us for the question).
                In this case, we can select any vertex as the starting vertex to see if it is connected to every other vertex.
                */
                for(int i=1;i<27;++i){if(reg[i]==1||reg[i]==-1)in = i;}
                if(in==-1)for(int i=1;i<27;++i){for(int j=1;j<27;++j)if(graph[i][j])in=i;} 

                //checkConnections() checks if every vertice is connected in a single graph.
                possible = checkConnections(in);
            }
            
            if (possible) System.out.println("Ordering is possible.");
            else System.out.println("The door cannot be opened.");
        }
    }

    static class IO {

        static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        public static int[][] next2dInt(int rows, int cols, String seperator) throws Exception {
            int[][] arr = new int[rows + 1][cols + 1];
            for (int i = 1; i <= rows; ++i) {
                arr[i] = nextIntArray(cols, seperator);
            }
            return arr;
        }

        public static int[] nextIntArray(int nInts, String seperator) throws IOException {
            String ints = br.readLine();
            String[] sArray = ints.split(seperator);
            int[] array = new int[nInts + 1];
            for (int i = 1; i <= nInts; ++i) {
                array[i] = Integer.parseInt(sArray[i - 1]);
            }
            return array;
        }

        public static long[] nextLongArray(int nLongs, String seperator) throws IOException {
            String longs = br.readLine();
            String[] sArray = longs.split(seperator);
            long[] array = new long[nLongs + 1];
            for (int i = 1; i <= nLongs; ++i) {
                array[i] = Long.parseLong(sArray[i - 1]);
            }
            return array;
        }

        public static double[] nextDoubleArray(int nDoubles, String seperator) throws IOException {
            String doubles = br.readLine();
            String[] sArray = doubles.split(seperator);
            double[] array = new double[nDoubles + 1];
            for (int i = 1; i <= nDoubles; ++i) {
                array[i] = Double.parseDouble(sArray[i - 1]);
            }
            return array;
        }

        public static char[] nextCharArray(int nChars, String seperator) throws IOException {
            String chars = br.readLine();
            String[] sArray = chars.split(seperator);
            char[] array = new char[nChars + 1];
            for (int i = 1; i <= nChars; ++i) {
                array[i] = sArray[i - 1].charAt(0);
            }
            return array;
        }

        public static int nextInt() throws IOException {
            String in = br.readLine();
            return Integer.parseInt(in);
        }

        public static double nextDouble() throws IOException {
            String in = br.readLine();
            return Double.parseDouble(in);
        }

        public static long nextLong() throws IOException {
            String in = br.readLine();
            return Long.parseLong(in);
        }

        public static int nextChar() throws IOException {
            String in = br.readLine();
            return in.charAt(0);
        }

        public static String nextString() throws IOException {
            return br.readLine();
        }

        public static void print(Object... o) {
            for (Object os : o) {
                System.out.print(os);
            }
        }

        public static void println(Object... o) {
            for (Object os : o) {
                System.out.print(os);
            }
            System.out.print("\n");
        }

        public static void printlnSeperate(String seperator, Object... o) {
            StringBuilder sb = new StringBuilder();
            sb.delete(sb.length() - seperator.length(), sb.length());
            System.out.println(sb);
        }
    }
}

Check sample cases:

2
4
isq
mri
bac
cab
10
ab
bc
cd
cd
cd
cd
dc
dc
dc
duck

Output:
(not possible output)
(possible)

1
2
abcd
dcba

Output:
(possible)