#include<iostream>
#include<fstream>
#include<limits>
#include<vector>
#include<algorithm>

using namespace std;

//利用鄰接表實現(xiàn)圖的算法

#define MAX_VEX_NUM 10
#define INF  INT_MAX


typedef int VertexType;

struct ArcNode{ //單鏈表結(jié)點結(jié)構(gòu)
     int    adjvex; //該弧所指向的頂點的位置
     ArcNode   *nextarc;//指向下一條弧的指針
     //InfoType     *info；      //該弧相關(guān)信息的指針
};


typedef struct  VNode{//頂點結(jié)構(gòu)
      int   data;//頂點信息
      ArcNode    *firstarc; //指向第一條依附該頂點的弧的指針
	  int   indegree;//入度
}VNode,AdjList[MAX_VEX_NUM];

typedef struct { //鄰接表結(jié)構(gòu)
       AdjList    vertices;
       int    vexnum,arcnum;   //圖的當(dāng)前頂點數(shù)和弧數(shù)
}ALGraph;


class Graph{
  public:
    Graph();
    Graph(const char*);
    void degree(vector<int>&,vector<int>&);
    int order();
    int size();
    void output();
	void tpsort(vector<int>id);
	int printDegree (const vector<int>id, const vector<int>od);
  private:
    ALGraph g;
	int Matrix[MAX_VEX_NUM][MAX_VEX_NUM];
};

Graph::Graph()
{
	cout<<"請輸入節(jié)點數(shù)：";
	cin>>g.vexnum;
	int m=0;
	for(int i=0;i<g.vexnum;i++)
	{
		g.vertices[i].data=i;
		ArcNode* p=new ArcNode();
	    g.vertices[i].firstarc=p;
		for(int j=0;j<g.vexnum;j++)
		{
			cout<<"Matrix["<<i<<']'<<'['<<j<<']'<<'=';
			cin>>Matrix[i][j];
			if(i==j && Matrix[i][j]!=0)
				Matrix[i][j]=0;
			if(Matrix[i][j]==1)
			{
				m++;
				p->adjvex=j;
                p->nextarc=new ArcNode();
				p=p->nextarc;
			}
			if(j==g.vexnum-1)
				p->nextarc=NULL;
		}
	}
  g.arcnum= m;
}

//**********************************************************
Graph::Graph(const char* f)
{
	ifstream in(f);
	int m=0;
	in>>g.vexnum;
	for(int i=0;i<g.vexnum;i++)
	{
		g.vertices[i].data=i;
		ArcNode* p=new ArcNode();
	    g.vertices[i].firstarc=p;
		for(int j=0;j<g.vexnum;j++)
		{
			in>>Matrix[i][j];
			if(i==j && Matrix[i][j]!=0)
				Matrix[i][j]=0;
			if(Matrix[i][j]==1)
			{
				m++;
				p->adjvex=j;
                p->nextarc=new ArcNode();
				p=p->nextarc;
			}
			if(j==g.vexnum-1)
				p->nextarc=NULL;
		}
	}
	g.arcnum = m;
}
//***********************************************************************
void Graph::degree(vector<int>& indeg,vector<int>& outdeg)
{
	for(int count=0;count<g.vexnum;count++)
	{
		indeg[count]=outdeg[count]=0;
	}
	for(int i=0;i<g.vexnum;i++)
	{
		for(int j=0;j<g.vexnum;j++)
		{
			if(Matrix[i][j]>0&&Matrix[i][j]<INF)
			{
				 indeg[j]++;
				 outdeg[i]++;
			}
		}
	}
}
//****************************************************************************
int Graph::order()
{
	return g.vexnum;
}
//****************************************************************************
int Graph::size()
{
	return g.arcnum;
}

//******************************************************************************
void Graph::output()
{
	cout<<"該圖的鄰接矩陣是："<<endl;
	for (int i=0;i<g.vexnum;i++)
	{
		for (int j=0; j<g.vexnum; j++)
		{
			cout<<Matrix[i][j]<<"  ";
		}
		cout<<endl;
	}
	cout<<"圖的節(jié)點數(shù)為:"<<g.vexnum<<endl;
    cout<<"圖的邊數(shù)為:"<<g.arcnum<<endl;
	cout<<"該圖的鄰接表表示為："<<endl;
	for(int count=0; count<g.vexnum;count++)
	{
		cout<<g.vertices[count].data+1<<"->";
		ArcNode* p=g.vertices[count].firstarc;
        while(p->nextarc!=NULL)
		{
			if(p->nextarc->nextarc!=NULL)
			{
				cout<<p->adjvex+1<<"->";
			}
			else
                cout<<p->adjvex+1;
			p=p->nextarc;
		}
		cout<<endl;
	}
	cout<<endl;
}
//********************************************************************************
void Graph::tpsort(vector<int>id)//拓?fù)渑判?{
	int top=-1,m=0,i,j;
	ArcNode *p=NULL;
	vector<int>::iterator it;
	for(i=0,it=id.begin();i<g.vexnum,it!=id.end();i++,it++)
	{
		g.vertices[i].indegree=*it;
	}
	for(i=0;i<g.vexnum;i++)
	{
		if(g.vertices[i].indegree==0)
		{
			g.vertices[i].indegree=top;
			top=i;
		}
	}
    cout<<endl;
	while(top!=-1)
	{
		m++;
		cout<<g.vertices[top].data+1<<" ";
		p=g.vertices[top].firstarc;
		top=g.vertices[top].indegree;
		while(p->nextarc!=NULL)
		{
			j=p->adjvex;
			g.vertices[j].indegree--;
			if(g.vertices[j].indegree==0)
			{
				g.vertices[j].indegree=top;
				top=j;
			}
			p=p->nextarc;
		}
	}
	if(m==g.vexnum)
	{
		cout<<"為拓?fù)湫蛄?"<<endl;
	}
	else
	{
		cout<<"拓?fù)湫蛄胁淮嬖?"<<endl;
	}
}
//**************************************************************************************
int Graph::printDegree (const vector<int>id, const vector<int>od)
{
	//輸出入度和出度
	for(int i=0;i<id.size();i++)
	{
		cout<<"第 "<<i+1<<" 個節(jié)點的入度為: "<<id[i]<<endl;
	}
	for(int j=0;j<od.size();j++)
	{
		cout<<"第 "<<j+1<<" 個節(jié)點的出度為: "<<od[j]<<endl;
	}
    return 0;
}