OJ Board

Code: Select all

#include <cstdlib>
#include <iostream>
#include <list>

using namespace std;

int main(int argc, char *argv[])
{
    int n, m, l, r, d, w, c = 0, x = 0;
    list<int> lista;
    
    while( cin >> n >> m ) {
        if( n == 0 and m == 0 )
            break;
            
            
        int *students[n+1];
        int religions[n+1], temp[n+1];
        c++; d = 1; w = 1;
        
        for( int i = 1; i <= n; i++ )
             students[i] = &x;
        
        for( int i = 0; i < m; i++ ) {
             cin >> l >> r;
             
             if( *students[l] == 0 and *students[r] == 0 ) {
                 religions[w] = d;
                 temp[d] = w;
                 students[r] = &religions[w];
                 if( r != l ) {
                     students[l] = &religions[w];
                     lista.push_front(l);
                 }
                 lista.push_front(r);
                 d++; w++;
             }
             else if( *students[r] == 0 ) {
                  students[r] = students[l];
                  lista.push_front(r);
             }
             else if( *students[l] == 0 ) {
                  students[l] = students[r];
                  lista.push_front(l);
             }
             else if( *students[l] != *students[r] ) {
                  religions[temp[*students[l]]] = *students[r];
                  d--;
             }
        }
        d = n-lista.size()+d-1;
        cout << "Case " << c << ": " << d << "\n";
        lista.clear();
    }
}

Code: Select all

Accepted

Code: Select all

import java.util.Scanner;

public class UbiquitousReligions {


  private static int[] rank = new int[50000], parent = new int[50000];
  private static int nSets;
  private static int[] stack = new int[10]; /*used as a simple stack for the path compression 
                                             enhancement of the union find algorithm. Since
                                             the rank of the sets will never be greater
                                             than 5 (thanks to path compression itself), 
                                             10 is big enough to store the whole stack.*/
  
  private static void makeSet(int maxNodes) {
    nSets = maxNodes;
    for (int i = 0; i < maxNodes; i++)
      parent[i] = i;
  }
  
  private static void union(int x, int y) {
    int xParent = findSet(x);
    int yParent = findSet(y);
    if (xParent != yParent) {
      link(xParent, yParent);
      nSets--;
    }
  }

  private static void link(int x, int y) {
    if (rank[x] > rank[y]) {
      parent[y] = x;
    } else {
      parent[x] = y;
      if (rank[x] == rank[y])
        rank[y]++;
    }
  }
  
  private static int findSet(int x) {
    int count = 0;
    while (x != parent[x]) {
      stack[count++] = x;
      x = parent[x];
    }
    while(--count > 0)
      parent[stack[count]] = x;
    return x;
  }
  
  
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    long m;
    int x, y, n, caseNumber = 0;
    while ((n = sc.nextInt()) != 0 && (m = sc.nextLong()) != 0) {
      makeSet(n);
      for (long i = 0; i < m; i++) {
        x = sc.nextInt();
        y = sc.nextInt();
        x--;
        y--;
        union(x,y);
      }
      caseNumber++;
      System.out.println("Case " + caseNumber + ": " + nSets);
    }
  }
}