A Bug's Life

From Progteam

Revision as of 07:31, 28 February 2007 by Hjfreyer (Talk | contribs)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to: navigation, search
Checkmark.jpg This problem has been solved by hjfreyer.


A Bug's Life
Problem Number 2492
Sorter: Uncategorized
Source: TUD Programming Contest 2005, Darmstadt, Germany
Link: http://acm.pku.edu.cn/JudgeOnline/problem?id=2492



A Bug's Life is problem number 2492 on the Peking University ACM site. The problem concerns interactions between bugs of supposedly different genders. The task is to find whether, given a list of interactions, it's possible that no two bugs of the same sex interacted.


Data Representation

Interaction is a dead giveaway that the data should be represented as a graph. Vertices represent bugs, and edges represent edges. Building such a graph is largely trivial. Each vertex is also given a color, representing the gender of the bug. Now the problem is to determine if, given our graph, can we color it with two colors such that no edge connects two vertices of the name color.

Algorithm

Main article: Two-Coloring

The graph is processed with a depth first search. When a node is visited, it is passed the color of it's parent. If the vertex has no color (has not yet been visited) then it sets its color to be the opposite of its parent's, and then recursively processes all nodes adjacent to it, passing them its color. If the node already has a color, and the color is the same as its parent's, the process has failed, and the graph is not two-colorable. If this condition never occurs, the graph is two-colorable.

Solution

A solution to the two-coloring approach appears below:


import java.util.*;

public class Main{

    public static Scanner in;
    public static StringBuilder out;

    public static Graph g;

    public static void main(String[] args){
        in=new Scanner(System.in);
        out=new StringBuilder();

        doStuff();
    }

    public static void doStuff(){
        int N=in.nextInt();

        for(int i=0;i<N;i++){
            System.out.println("Scenario #"+(i+1)+":");
            solve();
            System.out.println();
        }
    }

    /** Work actually done here */
    public static void solve(){
        int bugs=in.nextInt();
        int interacts=in.nextInt();

        g=new Graph(bugs);



        for(int i=0;i<interacts;i++){
            int bug1=in.nextInt()-1;
            int bug2=in.nextInt()-1;

            g.addEdge(bug1,bug2);
        }

        if(suspicious())
            System.out.println("Suspicious bugs found!");
        else
            System.out.println("No suspicious bugs found!");
    }
    
    static boolean suspicious(){
        for(Vertex x:g.verts){
            if(!x.visited&&suspicious(x,0))
                return true;
        }
        return false;
    }
    
    static boolean suspicious(Vertex v,int parentcolor){
        v.visited=true;

        if(-1!=v.color)  //Already colored
            return v.color==parentcolor;

        //Not colored, color me the opposite
        v.color=(0==parentcolor)?1:0;
	
        for(Vertex x:v){
            if(suspicious(x,v.color))
                return true;
        }
        return false;
    }
}

class Graph{
    /** Core Stuff **/
    public Vertex[] verts;

    public Graph(int order){
        verts=new Vertex[order];

        for(int i=0;i<order;i++){
            verts[i]=new Vertex();
        }
    }

    public void addEdge(Vertex i,Vertex j){
        i.adj.add(j);
        j.adj.add(i);
    }

    public void addEdge(int i,int j){
        addEdge(verts[i],verts[j]);
    }


    /** Optional Stuff **/

    public Vertex getFirst(){
        return verts[0];
    }

    public boolean isConnected(){
        return verts.length==countNodes(getFirst());
    }

    public int countNodes(Vertex v){
        if(v.visited)
            return 0;

        v.visited=true;

        int num=1;

        for(Vertex x:v){
            num+=countNodes(x);
        }

        return num;
    }
}

class Vertex implements Iterable<Vertex>{
    public boolean visited=false;
    public List adj;
    public int color=-1;

    public Vertex(){
        adj=new List();
    }

    public int degree(){
        return adj.size;
    }

    public Iterator<Vertex> iterator(){
        return adj.iterator();
    }

}

class List implements Iterable<Vertex>{

    class Node{
        Vertex el;
        Node next;
    }

    class Iter implements Iterator<Vertex>{
        Node ptr;

        public boolean hasNext(){
            return ptr.next!=null;
        }
        public Vertex next(){
            ptr=ptr.next;return ptr.el;
        }
        public void remove(){}
    }

    Node header;
    int size;

    public List(){
        header=new Node();
        header.next=null;
        size=0;
    }

    public boolean add(Vertex v){
        Node n=new Node();
        n.el=v;
        n.next=header.next;
        header.next=n;
        ++size;
        return true;
    }

    public Iter iterator(){
        Iter i=new Iter();
        i.ptr=header;
        return i;
    }
}

Personal tools