#include <iostream.h>
//#include "stack.h"
const int DefaultVertices=10000;
struct Edge{
int dest;
int cost;
Edge *link;
Edge(){}
Edge(int num,int sum):dest(num),cost(sum),link(NULL){}
bool operator !=(Edge &R)const{
return(dest!=R.dest)?true:false;///////////////////
}
};
struct Vertex{
int data;
Edge *adjacence;
Edge *source;
};
class LinkGraph{
friend istream& operator>>(istream& in,LinkGraph &G);
friend void TopologicalSort(LinkGraph &G);
friend void FindCircle(LinkGraph &G,const int &v);
friend bool DFS(LinkGraph &G,int v,int start,bool visited[]);
private:
// Stack <int> st;
Vertex *NodeTable;
int MaxVertices;
int NumEdges;
int NumVertices;
int Reverse[DefaultVertices];
public:
LinkGraph(int size=DefaultVertices);
~LinkGraph();
int NumberOfVertices();
int NumberOfEdges();
int GetValue(int i);
bool InsertVertex(const int &v);
bool InsertEdge(int v1,int v2);
int GetFirstNeighbor(int v);
int GetNextNeighbor(int v,int w);
int GetVertexPosition(const int vertex);
Edge *IsEdge(int v1,int v2);
};
LinkGraph::LinkGraph(int size){
int i=0;
MaxVertices=size;
NumVertices=0;
NumEdges=0;
NodeTable=new Vertex[MaxVertices];
if(NodeTable==NULL){
cout<<"Distributing memorry error!"<<endl;
}
for(i=0;i<MaxVertices;i++){
NodeTable[i].adjacence=NULL;
NodeTable[i].source=NULL;
}
for(i=0;i<DefaultVertices;i++)
Reverse[i]=-1;
};
LinkGraph::~LinkGraph(){
int i=0;
for(i=0;i<NumVertices;i++){
Edge *p=NodeTable[i].adjacence,*q=NodeTable[i].source;
while(p!=NULL){
NodeTable[i].adjacence=p->link;
delete p;
p=NodeTable[i].adjacence;
}
while(q!=NULL){
NodeTable[i].source=q->link;
delete q;
q=NodeTable[i].source;
}
}
delete []NodeTable;
};
int LinkGraph::NumberOfVertices(){
return NumVertices;
};
int LinkGraph::NumberOfEdges(){
return NumEdges;
};
int LinkGraph::GetValue(int i){
if(i>=0 && i<NumVertices)
return NodeTable[i].data;
else
return 0;
};
int LinkGraph::GetFirstNeighbor(int v){
if(v!=-1){
Edge *temp=NodeTable[v].adjacence;
if(temp!=NULL){
return temp->dest;
}
}
return -1;
};
int LinkGraph::GetNextNeighbor(int v,int w){
if(v!=-1){
Edge *temp=NodeTable[v].adjacence;
while(temp!=NULL&&temp->dest!=w){
temp=temp->link;
}
if(temp!=NULL&&temp->link!=NULL){
return temp->link->dest;
}
}
return -1;
};
bool LinkGraph::InsertVertex(const int &vertex){
if(NumVertices==MaxVertices)
return false;
NodeTable[NumVertices].data=vertex;
NumVertices++;
return 0;
};
bool LinkGraph::InsertEdge(int v1,int v2){
if(v1>=0&&v1<NumVertices&&v2>=0&&v2<NumVertices){
Edge *current,*temp=NodeTable[v1].adjacence;
while(temp!=NULL&&temp->dest!=v2)
temp=temp->link;
if(temp!=NULL)
return false;
temp=new Edge;
current=new Edge;
temp->dest=v2; //v2加入v1的出边表
temp->link=NodeTable[v1].adjacence;
NodeTable[v1].adjacence=temp;
current->dest=v1; //v1加入v2的入边表
current->link=NodeTable[v2].source;
NodeTable[v2].source=current;
NumEdges++;
return true;
}
return 0;
};
int LinkGraph::GetVertexPosition(const int vertex){
int i;
for(i=0;i<NumVertices;i++)
if(NodeTable[i].data==vertex)
return i;
return 0;
};
istream& operator>>(istream &in,LinkGraph &G){
int i=0,j,k,vertices,edges;
int v1,v2;
in>>vertices>>edges;
for(i=1;i<=vertices;i++)
G.InsertVertex(i);
i=0;
while(i<edges){
in>>v1>>v2;
j=G.GetVertexPosition(v1);
k=G.GetVertexPosition(v2);
if(j==-1||k==-1){
cout<<"Input error,try again!"<<endl;
}
else{
G.InsertEdge(j,k);
i++;
}
}
return in;
};
//函数判断G的v1,v2之间是否存在边
Edge *LinkGraph::IsEdge(int v1,int v2){
Edge *temp=NodeTable[v1].adjacence;
if(v1!=-1&&v2!=-1){
while(temp!=NULL){
if(temp->dest==v2)
return temp;
else
temp=temp->link;
}
}
return 0;
};
void FindCircle(LinkGraph &G,const int &v){
int i,sum=G.NumberOfVertices();
int temp=0;
bool *visited=new bool[sum];
for(i=0;i<sum;i++)
visited[i]=false;
// loc=G.GetVertexPosition(v);
for(int j=0;j<sum;j++){
if(DFS(G,j,j,visited)){
cout<<G.GetValue(j)<<",";
for(i=DefaultVertices-1;i>=0;i--){
if(G.Reverse[i]!=-1){
temp++;
}
}
int tank=0;
for(i=DefaultVertices-1;i>=0;i--){
if(G.Reverse[i]!=-1){
cout<<G.Reverse[i];
tank++;
if(tank!=temp)
cout<<",";
}
}
return;
}
}
delete []visited;
};
bool DFS(LinkGraph &G,int v,int start,bool visited[]){
visited[v]=true;
static int u=0;
int w=G.GetFirstNeighbor(v);
while(w!=-1){
if(visited[w]==false && w!=start){
if(DFS(G,w,start,visited))
{
G.Reverse[u++]=G.GetValue(w);
return 1;
}
}
if(w==start)
{
G.Reverse[u++]=G.GetValue(w);
return 1;
}
w=G.GetNextNeighbor(v,w);
}
return 0;
};
void TopologicalSort(LinkGraph &G){
int i,j,w,v,k=0;
int temp=0;
int top=-1; //度为零的顶点的初始化
int sum=G.NumberOfVertices();
int *buffer=new int [sum];
int *count=new int [sum]; //每个顶点的入度
for(i=0;i<sum;i++)
count[i]=0;
for(i=0;i<sum;i++){
for(j=0;j<sum;j++)
if(G.IsEdge(i,j))
count[j]++; //记录输入的图中每个顶点的入度
}
for(i=0;i<sum;i++){
if(count[i]==0){
count[i]=top; //入度为零的顶点进栈
top=i;
}
}
for(i=0;i<sum;i++){
if(top==-1){ //中途栈空了，弹出
cout<<"No..............//(Not A DAG)"<<endl;
FindCircle(G,i);
cout<<"........//(Circle)"<<endl;
cout<<endl;
return;
}
else{
v=top; //退栈
top=count[top];
buffer[k++]=G.GetValue(v);
w=G.GetFirstNeighbor(v);
while(w!=-1){ //出边表检查
if(--count[w]==0){ //邻接顶点如度减一，进栈
count[w]=top;
top=w;
}
w=G.GetNextNeighbor(v,w);
}
}
}
cout<<"Yes..........................//(DAG)"<<endl;
for(i=0;i<sum;i++){
cout<<buffer[i];
if(i!=G.NumberOfVertices()-1)
cout<<",";
}
cout<<"...//(Topological Odering!)"<<endl;
}
int main(){
LinkGraph LG;
// cout<<"Sample input:"<<endl;
// cout<<"(First line: n vertices, m directed edges;"<<endl;
// cout<<"Following m lines, x y means edge from vertex x to vertex y)"<<endl;
// cout<<endl;
cin>>LG;
TopologicalSort(LG);
return 0;
}
