assignment.java

用邻接矩阵的形式实现了求有向图的强连通分量。

package test;
import java.io.*;
import java.util.Stack;
import java.util.Vector;
/*
 * 求有向图的强连通分量
 * @author 周建勇
 */
class Vertex
{

    Vertex()
    {
        dfsN = 0;
        component = 0;
        high = 0;
        father = 0;
        marked = false;
    }

    public boolean isMarked()
    {
        return marked;
    }

    public void setMarked()
    {
        marked = true;
    }

    public int getdfsN()
    {
        return dfsN;
    }

    public void setdfsN(int dfsN)
    {
        this.dfsN = dfsN;
    }

    public int getComponent()
    {
        return component;
    }

    public void setComponent(int component)
    {
        this.component = component;
    }

    public int getHigh()
    {
        return high;
    }

    public void setHigh(int high)
    {
        this.high = high;
    }

    public int getFather()
    {
        return father;
    }

    public void setFather(int father)
    {
        this.father = father;
    }

    private int dfsN;
    private int component;
    private int high;
    private boolean marked;
    private int father;
}

class Edge
{

    Edge(int start, int end)
    {
        this.start = start;
        this.end = end;
        isScanned = false;
    }

    public boolean isScanned()
    {
        return isScanned;
    }

    public void setScanned()
    {
        isScanned = true;
    }

    public int getStart()
    {
        return start;
    }

    public int getEnd()
    {
        return end;
    }

    private int start;
    private int end;
    private boolean isScanned;
}

class Scc
{

    Scc(String filename)
    {
        initialize(filename);
    }

    public void initialize(String filename)
    {
        try
        {
            BufferedReader in = new BufferedReader(new FileReader(filename));
            String s = in.readLine();
            DFS_N = nVertex = Integer.parseInt(s);
            currentComponent = 0;
            n = 0;
            stack = new Stack<Integer>();
            scc = new Stack<Integer>();
            sccContainer = new Vector();
            size = new Vector();
            vertex = new Vertex[nVertex];
            adjMatrix = new int[nVertex][nVertex];
            Vector line = new Vector();
            for(int i = 0; i < nVertex; i++)
                vertex[i] = new Vertex();

            for(int i = 0; (s = in.readLine()) != null; i++)
            {
                filterInput(s.substring(1, s.length() - 1), line);
                nEdge = i + 1;
            }

            int tmp[] = new int[line.size()];
            vectorToInteger(line, tmp);
            edge = new Edge[nEdge];
            for(int i = 0; i < line.size(); i += 2)
            {
                adjMatrix[tmp[i]][tmp[i + 1]] = 1;
                edge[i / 2] = new Edge(tmp[i], tmp[i + 1]);
            }

            in.close();
        }
        catch(IOException e)
        {
            System.out.print("");
        }
    }

    public void scc()
    {
        for(int i = 0; i < nVertex; i++)
            if(vertex[i].getdfsN() == 0)
                scca(i);

        output();
    }

    public void scca(int v)
    {
        vertex[v].setdfsN(DFS_N);
        DFS_N--;
        stack.push(Integer.valueOf(v));
        vertex[v].setHigh(vertex[v].getdfsN());
        for(int i = 0; i < nEdge; i++)
            if(edge[i].getStart() == v && !edge[i].isScanned())
                if(vertex[edge[i].getEnd()].getdfsN() == 0)
                {
                    scca(edge[i].getEnd());
                    vertex[v].setHigh(Math.max(vertex[v].getHigh(), vertex[edge[i].getEnd()].getHigh()));
                } else
                if(vertex[edge[i].getEnd()].getdfsN() > vertex[v].getdfsN() && vertex[edge[i].getEnd()].getComponent() == 0)
                    vertex[v].setHigh(Math.max(vertex[v].getHigh(), vertex[edge[i].getEnd()].getdfsN()));

        if(vertex[v].getHigh() == vertex[v].getdfsN())
        {
            currentComponent++;
            int index;
            do
            {
                index = Integer.parseInt(stack.pop().toString());
                scc.push(Integer.valueOf(index));
                vertex[index].setComponent(currentComponent);
            } while(index != v);
            Vector<String> temp = new Vector<String>();
            while(!scc.isEmpty()) 
            {
                temp.addElement(scc.pop().toString());
                n++;
            }
            size.addElement(Integer.valueOf(v));
            n = 0;
            sccContainer.addElement(temp.toString());
        }
    }

    private void output()
    {
        try
        {
            PrintWriter out = new PrintWriter(new BufferedWriter(new FileWriter("result.txt")));
            inssort();
            out.println((new StringBuilder("Scc number: ")).append(sccContainer.size()).toString());
            for(int i = 0; i < sccContainer.size(); i++)
            {
                String s = sccContainer.elementAt(i).toString();
                out.println((new StringBuilder("(")).append(s.substring(1, s.length() - 1)).append(")").toString());
            }

            out.close();
        }
        catch(IOException e)
        {
            System.out.print("");
        }
    }

    private void swap(int left, int right)
    {
        Vector temp = new Vector();
        Vector temp1 = new Vector();
        temp.addElement(size.elementAt(left));
        size.setElementAt(size.elementAt(right), left);
        size.setElementAt(temp.elementAt(0), right);
        temp1.addElement(sccContainer.elementAt(left));
        sccContainer.setElementAt(sccContainer.elementAt(right), left);
        sccContainer.setElementAt(temp1.elementAt(0), right);
    }

    public void inssort()
    {
        for(int i = 1; i < sccContainer.size(); i++)
        {
            for(int j = i; j > 0 && Integer.parseInt(size.elementAt(j).toString()) > Integer.parseInt(size.elementAt(j - 1).toString()); j--)
                swap(j - 1, j);

        }

    }

    private void vectorToInteger(Vector line, int tmp[])
    {
        for(int i = 0; i < line.size(); i++)
            tmp[i] = Integer.parseInt(line.elementAt(i).toString());

    }

    private void filterInput(String s, Vector line)
    {
        int start = 0;
        for(int i = 0; i < s.length(); i++)
        {
            if(s.charAt(i) == ',')
            {
                line.add(s.substring(start, i));
                start = i + 1;
            }
            if(i == s.length() - 1)
                line.add(s.substring(start, i + 1));
        }

    }

    private int nVertex;
    private int nEdge;
    private int adjMatrix[][];
    private Vertex vertex[];
    private Edge edge[];
    private int currentComponent;
    private int DFS_N;
    private Stack<Integer> stack;
    private Stack<Integer> scc;
    private Vector sccContainer;
    private Vector size;
    private int n;
}
public class Assignment
{

    public Assignment()
    {
    }

    public static void main(String args[])
    {
        Scc test = new Scc("data.txt");
        test.scc();
    }
}