import java.io.*;
import java.util.*;
class task1{
public static void main(String[] args) throws Exception{
while(true){
BufferedReader bR = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(bR.readLine());
if(n == 0){break;}
GraphAdjLists GAL = new GraphAdjLists(bR,n);
}
}
}
/*
* Current implementation uses adjacency lists form of a graph.
*/class GraphAdjLists{
// Internal Representation and Constructors
//
protected ArrayList<ArrayList<Integer>> adj; public GraphAdjLists(){
adj = new ArrayList<ArrayList<Integer>>();
} public GraphAdjLists(Graph G){
int n = G.order();
adj = new ArrayList<ArrayList<Integer>>();
for (int i = 0; i < n; i++){
adj.add(G.neighbors(i));
}
}
public GraphAdjLists(BufferedReader buffer, int n){
try{
String line;
String[] tokens = null;
adj = new ArrayList<ArrayList<Integer>>(); for (int u = 0; u < n; u++)
{
ArrayList<Integer> current = new ArrayList<Integer>();
line = buffer.readLine().trim();
int limit = 0;
if (!line.equals(""))
{
tokens = line.split("\\s+");
limit = tokens.length;
} for (int i = 0; i < limit; i++)
{
current.add(Integer.parseInt(tokens[i]));
}
adj.add(current);
}
}
catch (IOException x)
{
throw new Error("bad input stream");
}
}
// Mutator Methods
//
public void addVertices(int n)
{
assert(0 <= n);
if ( n > 0 )
{
for (int i = 0; i < n; i++)
{
adj.add(new ArrayList<Integer>());
}
}
} public void removeVertex(int i)
{
assert(0 <= i && i < order());
adj.remove(i);
Integer I = new Integer(i);
for (int u = 0; u < order(); u++)
{
ArrayList<Integer> current = adj.get(u);
current.remove(I); // remove i from adj lists
for (Integer num: current)
{
if (num > i) // relabel larger indexed nodes
{
int index = current.indexOf(num);
current.set(index, num-1);
}
}
}
} public void addArc(int i, int j)
{
assert(0 <= i && i < order());
assert(0 <= j && j < order());
if (isArc(i,j)) return;
(adj.get(i)).add(j);
} public void removeArc(int i, int j)
{
assert(0 <= i && i < order());
assert(0 <= j && j < order());
if (!isArc(i,j)) return;
(adj.get(i)).remove(new Integer(j));
} public void addEdge(int i, int j)
{
assert(0 <= i && i < order());
assert(0 <= j && j < order());
if (!isArc(i,j)) (adj.get(i)).add(j);
if (!isArc(j,i)) (adj.get(j)).add(i);
} public void removeEdge(int i, int j)
{
assert(0 <= i && i < order());
assert(0 <= j && j < order());
if (isArc(i,j)) (adj.get(i)).remove(new Integer(j));
if (isArc(j,i)) (adj.get(j)).remove(new Integer(i));
}
// Access Methods
//
public boolean isArc(int i, int j)
{
assert(0 <= i && i < order());
assert(0 <= j && j < order());
return (adj.get(i)).contains(new Integer(j));
} public boolean isEdge(int i, int j)
{
assert(0 <= i && i < order());
assert(0 <= j && j < order());
return isArc(i,j) && isArc(j,i);
} public int inDegree(int i)
{
assert(0 <= i && i < order());
int sz = 0;
for (int j = 0; j < order(); j++)
{
if (isArc(j,i)) sz++;
}
return sz;
} public int degree(int i)
{
assert(0 <= i && i < order());
return (adj.get(i)).size();
} public ArrayList<Integer> neighbors(int i)
{
assert(0 <= i && i < order());
ArrayList<Integer> nei = new ArrayList<Integer>();
for (Integer vert : adj.get(i))
{
nei.add(vert);
}
return nei;
} public int order()
{
return adj.size();
} public int size() // Number of arcs (counts edges twice).
{
int sz = 0;
for (int i=0; i<order(); i++)
{
sz += (adj.get(i)).size();
}
return sz;
} // default output readable by constructor
//
public String toString()
{
return toStringAdjLists();
}
public String toStringAdjLists()
{
StringBuffer o = new StringBuffer();
o.append(order()+"\n"); for (int i = 0; i < order(); i++)
{
ArrayList<Integer> nei = neighbors(i);
for (int j : nei)
{
o.append(j + " ");
}
o.append("\n");
}
return o.toString();
}
}
有向图的实现大概是这样吧,用一层ArrayList储存节点然后里面再用一层ArrayList作为相邻的节点。
运行的时候第一个数字是节点个数,然后之后每一行就是相邻节点的KEY,节点的KEY从0开始。如果一个图建成后用户输入0就退出程序。譬如:
5
1
2
3
4
0
这串数字输入后是一个有5个节点的图,有向边是0-->1-->2-->3-->4-->0
程序的目的有3个:1.计算有多少个连通分量(不是强连通分量也行)2.计算从0开始最长的路径 3.计算从0到最大KEY的节点有多少条路径
如果可以的话,能不能把这几个问题解决呢?不行的话,哪怕只是写一个深度遍历和广度遍历也很感激了。谢谢!
public void DFS(){
for (int i = 0; i < order(); i++){
state[i] = VertexState.White;
}
int time = 0;
for(int u = 0;u<order();u++){
time = recursiveDFS(u,time);
}
int[] topo = topoSort(doneTimes);
System.out.println(longestPath(0,topo));
}
public int recursiveDFS(int u,int time){
if(state[u] != VertexState.White){
return time;
}
state[u] = VertexState.Gray;
//System.out.format("%d is seen, time is %d\n",u,time);
seenTimes[u] = time;
time++;
int lastTime = time;
for(int v = 0; v < order(); v++){
if(isArc(u, v) && state[v] == VertexState.White){
pred[v] = u;
time = recursiveDFS(v,time);
}
}
if(lastTime == time){
leavesSeenTimes.add(time-1);
}
//System.out.format("%d is done, time is %d\n",u,time);
state[u] = VertexState.Black;
doneTimes[u] = time;
time++;
return time;
}