#include <iostream>
#include <cstdio>
#include <string>
#include <string.h>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
typedef long long ll;
const int  maxn = 10005;
const int  mod = 7654321;

typedef int ElementType;

typedef struct Node
{
	ElementType data[maxn];//元素
	int last;//最后一個(gè)元素的下標(biāo)
}*List;

/*typedef是類(lèi)型定義的意思。typedef struct 是為了使用這個(gè)結(jié)構(gòu)體方便。
具體區(qū)別在于:
若struct node{}這樣來(lái)定義結(jié)構(gòu)體的話。在申請(qǐng)node 的變量時(shí)，需要這樣寫(xiě)，struct node n;
若用typedef，可以這樣寫(xiě)，typedef struct node {}NODE; 。在申請(qǐng)變量時(shí)就可以這樣寫(xiě)，NODE n;
區(qū)別就在于使用時(shí)，是否可以省去struct這個(gè)關(guān)鍵字。*/

//初始化一個(gè)空表
List CreatList()
{
	List L;
	L = (List)new int();
	//開(kāi)辟一塊新空間
	L->last = -1;
	return L;
}

//查找
ElementType Search(List L, ElementType x)
{
	int i = 0;
	while (i <= L->last)
	{
		if (L->data[i] == x)
			return i;
		i++;
	}
	return -1;
}

//插入
bool Insert(List L, int position, ElementType x)
{
	if (L->last == maxn - 1)
	{
		cout << "表已滿" << endl;
		return false;
	}
	if (position<0 || position>L->last + 1)
	{
		cout << "位置不合法" << endl;
		return false;
	}
	for (int i = L->last; i >= position; i--)
	{
		L->data[i + 1] = L->data[i];
	}
	L->data[position] = x;
	L->last++;
	return true;
}
//刪除
bool Delet(List L, int position)
{
	if (position<0 || position>L->last)
	{
		cout << "位置不合法" << endl;
		return false;
	}
	for (int i = position + 1; i <= L->last; i++)
	{
		L->data[i - 1] = L->data[i];
	}
	L->last--;
	return true;
}

int main()
{
	List L = CreatList();
	Insert(L, 0, 1);
	Insert(L, 1, 1);
	Insert(L, 2, 2);
	cout << L->data[0] << endl;
	Delet(L, 1);
	cout << L->data[1] << endl;

	cout << Search(L, 2) << endl;

	return 0;
}

//首先中轉(zhuǎn)站C中，車(chē)廂符合先進(jìn)后出的原則，是一個(gè)棧
#include<cstdio>
#include<stack>
using namespace std;
const int maxn = 1000 + 10;
int n, target[maxn];

int main()
{
	while (scanf_s("%d", &n) == 1)
	{
		stack<int> s;
		int a = 1, b = 1;
		for (int i = 1; i <= n; i++)
		{
			scanf_s("%d", &target[i]);
		}
		int ok = 1;
		while (b <= n)
		{
			if (a == target[b])
			{
				a++;
				b++;
			}
			else if (!s.empty() && s.top() == target[b])
			//運(yùn)用empty和top函數(shù)，包含頭文件《stack》
			{
				s.pop();
				b++;

			}
			else if (a <= n)
				s.push(a++);
			else
			{
				ok = 0;
				break;
			}
	}
		printf("%s\n", ok ? "yes" : "no");

	}
	return 0;
}

#include <iostream>
#include <stack>
using namespace std;
//表達(dá)式求值                                                                     
const int MaxSize = 100;
void trans(char exp[], char postexp[])
{
	stack<char> op;
	int i = 0, j = 0;
	//op.top = -1;
	while (*exp != '\0')
	{
		switch (*exp)
		{
		case '('://左括號(hào)進(jìn)棧
			op.push(*exp);
			exp++;
			break;
		case ')'://將棧中“（”以前的運(yùn)算符依次刪除存入數(shù)組exp中，然后將“（”刪除
			while (!op.empty() && op.top() != '(')
			{
				postexp[i++] = op.top();
				op.pop();
			}
			op.pop();
			exp++;
			break;
		case '+':
		case '-':
			while (!op.empty() && op.top() != '(')
			{//將棧中優(yōu)先級(jí)大于等于‘+'或'-'的運(yùn)算符退棧并存放到postexp中
				postexp[i++] = op.top();
				op.pop();
			}
			op.push(*exp);
			exp++;
			break;
		case '*':
		case '/':
			while (!op.empty() && (op.top() == '*' || op.top() == '/'))
			{//將棧中的“*”或者是“/”運(yùn)算符依次出棧并存放到postexp中
				postexp[i++] = op.top();
				op.pop();
			}
			op.push(*exp);
			exp++;
			break;
		case ' ':break;
		default:
			while (isdigit(*exp))
			{
				postexp[i++] = *exp;
				exp++;
			}
			postexp[i++] = '#';
		}
	}
	while (!op.empty())//最后的掃描工作
	{
		postexp[i++] = op.top();;
		op.pop();;
	}
	postexp[i] = '\0';
	cout << "后綴表達(dá)式" << endl;
	for (j = 0; j < i; j++)
	{
		if (postexp[j] == '#')
			j++;
		cout << postexp[j];
	}
	cout << endl;
}

float compvalue(char postexp[])
{
	stack<float> st;
	float a, b, c, d;

	while (*postexp != '\0')
	{
		switch (*postexp)
		{
		case '+':
			a = st.top();
			st.pop();
			b = st.top();;
			st.pop();;
			c = a + b;
			st.push(c);
			break;

		case '-':
			a = st.top();
			st.pop();
			b = st.top();;
			st.pop();;
			c = b - a;
			st.push(c);
			break;

		case '*':
			a = st.top();
			st.pop();
			b = st.top();;
			st.pop();;
			c = a * b;
			st.push(c);
			break;

		case '/':
			a = st.top();
			st.pop();
			b = st.top();;
			st.pop();;
			if (a != 0)
			{
				c = b / a;
				st.push(c);
			}
			else
			{
				cout << "除零錯(cuò)誤!" << endl;
				exit(0);
			}
			break;
		default://進(jìn)行最后的掃尾工作，將數(shù)字字符轉(zhuǎn)換成數(shù)值存放到d中
			d = 0;
			while (isdigit(*postexp))
			{
				d = 10 * d + *postexp - '0';
				postexp++;
			}
			st.push(d);
			break;

		}
		postexp++;
	}
	return (st.top());
}

int main()
{
	char exp[MaxSize] = "((18+6)*2-9)/2";
	char postexp[MaxSize] = { 0 };
	trans(exp, postexp);//exp存放中綴表達(dá)式,postexp存放后綴表達(dá)式
	printf("后綴表達(dá)式的值\n");
	printf("%.2f\n", compvalue(postexp));
	return 0;
}

#include<cstdio>
#include<cstring>
int a[100010][3],n,m;
//a[i][2]表示學(xué)號(hào)為i的同學(xué)右邊同學(xué)的學(xué)號(hào)
//a[i][3]表示學(xué)號(hào)為i的同學(xué)左邊同學(xué)的學(xué)號(hào)
int main()
{
    scanf("%d",&n); 
    int j=1;
    memset(a,0,sizeof(a));
    a[1][1]=1;
    for(int i=2;i<=n;i++)
    {
        int x,y; scanf("%d %d",&x,&y);
        a[i][1]=i;
        if(y==0)
        //插入左邊
        { 
            a[a[x][3]][2]=i; a[i][2]=x;
            a[i][3]=a[x][3]; a[x][3]=i;
            if(x==j) j=i;
            //比較麻煩，要改鏈表
        }
        else
        //插入右邊
        {
            a[i][2]=a[x][2]; a[a[x][2]][3]=i;
            a[x][2]=i; a[i][3]=x;
        }
    }
    scanf("%d",&m);
    for(int i=1;i<=m;i++)
    {
        int x; scanf("%d",&x);
        if(a[x][1]!=0)
        //該同學(xué)還在 
        {
            a[x][1]=0;
            //踢掉
            a[a[x][3]][2]=a[x][2];
            a[a[x][2]][3]=a[x][3];
            n--;
            if(x==j) j=a[x][3];
        }
    }
    int i=1,x=j;
    while(i<=n)
    {
        printf("%d ",a[x][1]);
        x=a[x][2]; i++;
    }
    return 0;
}

//在c中許多是要單獨(dú)寫(xiě)的，但是c++引入了string，其中包含了許多函數(shù)就不用自己直接寫(xiě)了，為了學(xué)習(xí)我先用c寫(xiě)，之后講解c++的string
#include <iostream>
#include <string>
using namespace std;
int main ()
{
    int size = 0;
    int length = 0;
    unsigned long maxsize = 0;
    int capacity=0;
    string str ("12345678");
    string str_custom;
    str_custom = str;
    str_custom.resize (5);
    size = str_custom.size();//大小
    length = str_custom.length();//長(zhǎng)度
  
    cout << "size = " << size << endl;
    cout << "length = " << length << endl;
    return 0;
}

int i = pos;
int j = 1;
while (i <= s[0] && j <= t[0])//當(dāng)i<s的長(zhǎng)度，且j<t的長(zhǎng)度，循環(huán)繼續(xù)
{
	if (s[i] = t[j])
	{
		i++;
		j++;//繼續(xù)
	}
	else//缺點(diǎn)：后退重新匹配
	{
		i = i - j + 2;//i回到上次匹配首位的下一位
		j = 1;//回到首位
	}
}
if (j > t[0])
return i - t[0];//不匹配
else
return 0;

typedef struct
{	
	char data[MaxSize];
	int length;			//串長(zhǎng)
} SqString;
//SqString 是串的數(shù)據(jù)結(jié)構(gòu)
//typedef重命名結(jié)構(gòu)體變量，可以用SqString t定義一個(gè)結(jié)構(gòu)體。
void GetNext(SqString t,int next[])		//由模式串t求出next值
{
	int j,k;
	j=0;k=-1;
	next[0]=-1;//第一個(gè)字符前無(wú)字符串，給值-1
	while (j<t.length-1) 
	//因?yàn)閚ext數(shù)組中j最大為t.length-1,而每一步next數(shù)組賦值都是在j++之后
	//所以最后一次經(jīng)過(guò)while循環(huán)時(shí)j為t.length-2
	{	
		if (k==-1 || t.data[j]==t.data[k]) 	//k為-1或比較的字符相等時(shí)
		{	
			j++;k++;
			next[j]=k;
			//對(duì)應(yīng)字符匹配情況下，s與t指向同步后移
			//通過(guò)字符串"aaaaab"求next數(shù)組過(guò)程想一下這一步的意義
			//printf("(1) j=%d,k=%d,next[%d]=%d\n",j,k,j,k);
       	}
       	else
		{
			k=next[k];
			**//我們現(xiàn)在知道next[k]的值代表的是下標(biāo)為k的字符前面的字符串最長(zhǎng)相等前后綴的長(zhǎng)度
			//也表示該處字符不匹配時(shí)應(yīng)該回溯到的字符的下標(biāo)
			//這個(gè)值給k后又進(jìn)行while循環(huán)判斷，此時(shí)t.data[k]即指最長(zhǎng)相等前綴后一個(gè)字符**
			//為什么要回退此處進(jìn)行比較，我們往下接著看。其實(shí)原理和上面介紹的KMP原理差不多
			//printf("(2) k=%d\n",k);
		}
	}
}
//kmp
int KMPIndex(SqString s,SqString t)  //KMP算法
{

	int next[MaxSize],i=0,j=0;
	GetNext(t,next);
	while (i<s.length && j<t.length) 
	{
		if (j==-1 || s.data[i]==t.data[j]) 
		{
			i++;j++;  			//i,j各增1
		}
		else j=next[j]; 		//i不變,j后退，現(xiàn)在知道為什么這樣讓子串回退了吧
    }
    if (j>=t.length)
		return(i-t.length);  	//返回匹配模式串的首字符下標(biāo)
    else  
		return(-1);        		//返回不匹配標(biāo)志
}

#include<iostream>
#include<cstring>
#define MAXN 1000010
using namespace std;
int kmp[MAXN];
int la,lb,j; 
char a[MAXN],b[MAXN];
int main()
{
    cin>>a+1;
    cin>>b+1;
    la=strlen(a+1);
    lb=strlen(b+1);
    for (int i=2;i<=lb;i++)
	   {     
	   while(j&&b[i]!=b[j+1])
        j=kmp[j];    
       if(b[j+1]==b[i])j++;    
        kmp[i]=j;
       }
    j=0;
    for(int i=1;i<=la;i++)
	   {
          while(j>0&&b[j+1]!=a[i])
           j=kmp[j];
          if (b[j+1]==a[i]) 
           j++;
          if (j==lb) {cout<<i-lb+1<<endl;j=kmp[j];}
       }

    for (int i=1;i<=lb;i++)
    cout<<kmp[i]<<" ";
    return 0;
}

/*
Project: Tree_parent(樹(shù)-雙親表示法)
Date:    2019/02/25
Author:  Frank Yu
基本操作函數(shù)：
InitTree(Tree &T) 參數(shù)T，樹(shù)根節(jié)點(diǎn) 作用：初始化樹(shù)，先序遞歸創(chuàng)建
InsertNode(Tree &T, TElemType node) 插入樹(shù)的結(jié)點(diǎn) 參數(shù)：樹(shù)T,結(jié)點(diǎn)node 作用：在雙親數(shù)組中插入結(jié)點(diǎn)，增加樹(shù)的結(jié)點(diǎn)值
InsertParent(Tree &T, TElemType node1, TElemType node2)//插入雙親數(shù)組的雙親域 參數(shù)：樹(shù)T ，結(jié)點(diǎn)node1,結(jié)點(diǎn)node2
                                                       //作用：使雙親數(shù)組中,node2對(duì)應(yīng)的雙親域?yàn)閚ode1的下標(biāo)
GetIndegree(Tree &T, TElemType node)                   //得到某結(jié)點(diǎn)入度 參數(shù)：樹(shù)T，結(jié)點(diǎn)node 結(jié)點(diǎn)不存在返回-1
GetOutdegree(Tree &T, TElemType node)                  //得到某結(jié)點(diǎn)出度 參數(shù)：樹(shù)T，結(jié)點(diǎn)node 結(jié)點(diǎn)不存在返回-1
PreOrder(Tree T)  參數(shù)：樹(shù)T,根節(jié)點(diǎn)下標(biāo) 作用：先序遍歷樹(shù)
PostOrder(Tree T) 參數(shù)：樹(shù)T,根節(jié)點(diǎn)下標(biāo) 作用：后序遍歷樹(shù)
LevelOrder(Tree T)參數(shù)：樹(shù)T            作用：層序遍歷樹(shù)
功能實(shí)現(xiàn)函數(shù)：
CreateTree(Tree &T) 參數(shù)T，樹(shù)根節(jié)點(diǎn) 作用：創(chuàng)建樹(shù)，調(diào)用InsertNode,InsertParent
Traverse(Tree T)    參數(shù)T，樹(shù)根節(jié)點(diǎn) 作用：PreOrder InOrder PostOrder LevelOrder遍歷樹(shù)
*/
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<string>
#include<stack>
#include<queue>
#include<algorithm>
#include<iostream>
#define TElemType char
#define Max 100
using namespace std;
//樹(shù)的結(jié)點(diǎn)數(shù)據(jù)結(jié)構(gòu)
typedef struct TNode
{
	TElemType data;//數(shù)據(jù)域
	int parent;    //雙親
}TNode;
//樹(shù)的數(shù)據(jù)結(jié)構(gòu)
typedef struct Tree
{
 
	TNode parent[Max];
	int NodeNum;
 
}Tree;
//********************************基本操作函數(shù)********************************//
//初始化樹(shù)函數(shù) 參數(shù)：樹(shù)T 作用：規(guī)定數(shù)據(jù)域?yàn)?，則為空，雙親為-1,則為空
void InitTree(Tree &T)
{
	for (int i=0;i<Max;i++)
	{
		T.parent[i].data = '#';
		T.parent[i].parent = -1;
	}
	T.NodeNum = 0;
}
//插入樹(shù)的結(jié)點(diǎn) 參數(shù)：樹(shù)T,結(jié)點(diǎn)node 作用：在雙親數(shù)組中插入結(jié)點(diǎn)，增加樹(shù)的結(jié)點(diǎn)值
bool InsertNode(Tree &T, TElemType node)
{
	
	if (node != '#')
	{
		T.parent[T.NodeNum++].data = node;//插入到雙親數(shù)組中
		return true;
	}
	return false;
}
//插入雙親數(shù)組的雙親域 參數(shù)：樹(shù)T ，結(jié)點(diǎn)node1,結(jié)點(diǎn)node2
//作用：使雙親數(shù)組中,node2對(duì)應(yīng)的雙親域?yàn)閚ode1的下標(biāo)
bool InsertParent(Tree &T, TElemType node1, TElemType node2)
{
	int place1, place2;
	place1 = -1;place2 = -1;
	for (int i=0;i<T.NodeNum;i++)//查找兩點(diǎn)是否存在
	{
		if (node1 == T.parent[i].data)place1 = i;
		if (node2 == T.parent[i].data)place2 = i;
	}
	if (place1 != -1 && place2 != -1)//兩點(diǎn)均存在
	{
		T.parent[place2].parent = place1;
		return true;
	}
	return false;
}
//得到某結(jié)點(diǎn)入度 參數(shù)：樹(shù)T，結(jié)點(diǎn)node 結(jié)點(diǎn)不存在返回-1
int GetIndegree(Tree &T, TElemType node)
{
	int place = -1;
	for (int i = 0;i<T.NodeNum;i++)
	{
		if (T.parent[i].data == node)place = i;
	}
	if (place!=-1)//結(jié)點(diǎn)存在
	{
		if(T.parent[place].parent!=-1)return 1;//雙親只能有一個(gè)
		else return 0; //根節(jié)點(diǎn)沒(méi)有雙親，即沒(méi)有入度
	}
	return -1;
}
//得到某結(jié)點(diǎn)出度 參數(shù)：樹(shù)T，結(jié)點(diǎn)node 結(jié)點(diǎn)不存在返回-1
int GetOutdegree(Tree &T, TElemType node)
{
	int place = -1;
	int outdegree = 0;
	for (int i = 0;i<T.NodeNum;i++)
	{
		if (T.parent[i].data == node)place = i;
	}
	if (place != -1)
	{
		for (int i = 0;i < T.NodeNum;i++)
		{
			if (T.parent[i].parent == place)outdegree++;
		}
		return outdegree;
	}
	return -1;
}
//先序遍歷 參數(shù)：樹(shù)T,根節(jié)點(diǎn)下標(biāo)
void PreOrder(Tree T,int i)
{
	if (T.NodeNum != 0)
	{
		cout << T.parent[i].data << " ";
		for(int j=0;j<T.NodeNum;j++)
		{
		  if(T.parent[j].parent==i)
		  PreOrder(T,j);//按左右先序遍歷子樹(shù)
		}
	}
}
//后序遍歷 參數(shù)：樹(shù)T,根節(jié)點(diǎn)下標(biāo)
void PostOrder(Tree T,int i)
{
	if (T.NodeNum != 0)
	{
		
		for (int j = 0;j<T.NodeNum;j++)
		{
			if (T.parent[j].parent == i)
				PostOrder(T, j);//按左右先序遍歷子樹(shù)
		}
		cout << T.parent[i].data << " ";
	}
}
//層序遍歷 參數(shù)：樹(shù)T
void LevelOrder(Tree T)
{
	queue<TNode> q;//借助隊(duì)列
	if (T.NodeNum!=0)
	{
		TNode temp;//暫存要出隊(duì)的結(jié)點(diǎn)
		q.push(T.parent[0]);//根結(jié)點(diǎn)入隊(duì)
		while (!q.empty())//隊(duì)列非空
		{
			temp = q.front();
			q.pop();
			cout<<temp.data<<" ";
			for (int j = 0;j<T.NodeNum;j++)
			{
				if (T.parent[T.parent[j].parent].data == temp.data)//當(dāng)前結(jié)點(diǎn)的父節(jié)點(diǎn)的數(shù)據(jù)域與彈出的相同 
					//因?yàn)閠emp沒(méi)有保存下標(biāo)，只能按這種方式比較，默認(rèn)結(jié)點(diǎn)名稱(chēng)不同
					q.push(T.parent[j]);//隊(duì)列先進(jìn)先出，先入左孩子
			}
		}
	}
}
//**********************************功能實(shí)現(xiàn)函數(shù)*****************************//
//創(chuàng)建樹(shù)，調(diào)用InsertNode,InsertParent
void CreateTree(Tree &T)
{
	int nodenum = 0;
	int parent;
	TElemType node,node1,node2;
	printf("請(qǐng)輸入樹(shù)的結(jié)點(diǎn)個(gè)數(shù):");
	cin >> nodenum;
	parent = nodenum - 1;
	printf("請(qǐng)輸入樹(shù)的結(jié)點(diǎn)名稱(chēng)（空格隔開(kāi)）:");
	while (nodenum--)
	{
		cin >> node;
		InsertNode(T,node);
	}
	printf("請(qǐng)輸入樹(shù)的結(jié)點(diǎn)間的雙親關(guān)系（一對(duì)為一雙親關(guān)系，A B表示A為B的雙親）:\n");
	while (parent--)
	{
		cin >> node1>>node2;
		InsertParent(T,node1,node2);
	}
	printf("\n");
}
//入度
void Indegree(Tree &T)
{
	TElemType node;
	int indegree;
	printf("請(qǐng)輸入結(jié)點(diǎn)名稱(chēng):\n");
	cin >> node;
	indegree = GetIndegree(T, node);
	if (-1 != indegree)
		cout << "該結(jié)點(diǎn)入度為：" << indegree << endl;
	else
		cout << "結(jié)點(diǎn)不存在。" << endl;
}
//出度
void Outdegree(Tree &T)
{
	TElemType node;
	int outdegree;
	printf("請(qǐng)輸入結(jié)點(diǎn)名稱(chēng):\n");
	cin >> node;
	outdegree = GetOutdegree(T, node);
	if (-1 != outdegree)
		cout << "該結(jié)點(diǎn)出度為：" << outdegree << endl;
	else
		cout << "結(jié)點(diǎn)不存在。" << endl;
}
//遍歷功能函數(shù) 調(diào)用PreOrder InOrder PostOrder LevelOrder
void Traverse(Tree T)
{
	int choice;
	while (1)
	{
		printf("********1.先序遍歷    2.后序遍歷*********\n");
		printf("********3.層次遍歷    4.返回上一單元*********\n");
		printf("請(qǐng)輸入菜單序號(hào)：\n");
		scanf("%d", &choice);
		if (4 == choice) break;
		switch (choice)
		{
		case 1: {printf("樹(shù)先序遍歷序列:");PreOrder(T,0);printf("\n");}break;
		case 2: {printf("樹(shù)后序遍歷序列:");PostOrder(T,0);printf("\n");}break;
		case 3: {printf("樹(shù)層序遍歷序列:");LevelOrder(T);printf("\n");}break;
		default:printf("輸入錯(cuò)誤?。。n");break;
		}
	}
}
//菜單
void menu()
{
	printf("********1.創(chuàng)建     2.某點(diǎn)入度*********\n");
	printf("********3.某點(diǎn)出度 4.遍歷*************\n");
	printf("********5.退出\n");
}
//主函數(shù)
int main()
{
	Tree T;
	int choice = 0;
	InitTree(T);
	while (1)
	{
		menu();
		printf("請(qǐng)輸入菜單序號(hào)：\n");
 
		scanf("%d", &choice);
		if (5 == choice) break;
		switch (choice)
		{
		case 1:CreateTree(T);break;
		case 2:Indegree(T);break;
		case 3:Outdegree(T);break;
		case 4:Traverse(T);break;
		default:printf("輸入錯(cuò)誤?。?！\n");break;
		}
	}
	return 0;
}

//指針域的個(gè)數(shù)就等于樹(shù)的度，其中樹(shù)的度又等于樹(shù)各個(gè)結(jié)點(diǎn)度的最大值
struct ChildNode
{
	int data；
	ChildNode*;
}
ChildNode *D;//d為最大結(jié)點(diǎn)
d.ChildNode;

struct Node
{
	int data;
	*firstchild,*ringtsib;
}
Node *Tree;

 struct BinaryTreeNode
   {
    struct BinTreeNode* _pLeft; // 指向當(dāng)前節(jié)點(diǎn)左孩子
    struct BinTreeNode* _pRight; // 指向當(dāng)前節(jié)點(diǎn)右孩子
    BTDataType _data; // 當(dāng)前節(jié)點(diǎn)值域
   }

BinaryTreeNode *tree;

typedef char BTDataType;

typedef struct BinaryTreeNode
{
	BTDataType _data;
	struct BinaryTreeNode* _left;
	struct BinaryTreeNode* _right;
}BTNode;

typedef BTNode* QDataType;
// 鏈?zhǔn)浇Y(jié)構(gòu)：表示隊(duì)列 
typedef struct QListNode
{
	struct QListNode* _next;
	QDataType _data;
}QNode;

// 隊(duì)列的結(jié)構(gòu) 
typedef struct Queue
{
	QNode* _front;
	QNode* _rear;
}Queue;

BTNode* CreateBTNode(BTDataType x);
// 通過(guò)前序遍歷的數(shù)組"ABD##E#H##CF##G##"構(gòu)建二叉樹(shù)
BTNode* BinaryTreeCreate(BTDataType* a, int n, int* pi);
// 二叉樹(shù)銷(xiāo)毀
void BinaryTreeDestory(BTNode** root);
// 二叉樹(shù)節(jié)點(diǎn)個(gè)數(shù)
int BinaryTreeSize(BTNode* root);
// 二叉樹(shù)葉子節(jié)點(diǎn)個(gè)數(shù)
int BinaryTreeLeafSize(BTNode* root);
// 二叉樹(shù)第k層節(jié)點(diǎn)個(gè)數(shù)
int BinaryTreeLevelKSize(BTNode* root, int k);
// 二叉樹(shù)查找值為x的節(jié)點(diǎn)
BTNode* BinaryTreeFind(BTNode* root, BTDataType x);
// 二叉樹(shù)前序遍歷 
void BinaryTreePrevOrder(BTNode* root);
// 二叉樹(shù)中序遍歷
void BinaryTreeInOrder(BTNode* root);
// 二叉樹(shù)后序遍歷
void BinaryTreePostOrder(BTNode* root);

// 初始化隊(duì)列 
void QueueInit(Queue* q);
// 隊(duì)尾入隊(duì)列 
void QueuePush(Queue* q, QDataType data);
// 隊(duì)頭出隊(duì)列 
void QueuePop(Queue* q);
// 獲取隊(duì)列頭部元素 
QDataType QueueFront(Queue* q);
// 獲取隊(duì)列隊(duì)尾元素 
QDataType QueueBack(Queue* q);
// 獲取隊(duì)列中有效元素個(gè)數(shù) 
int QueueSize(Queue* q);
// 檢測(cè)隊(duì)列是否為空，如果為空返回非零結(jié)果，如果非空返回0 
int QueueEmpty(Queue* q);
// 銷(xiāo)毀隊(duì)列 
void QueueDestroy(Queue* q);

// 層序遍歷
void BinaryTreeLevelOrder(BTNode* root);
// 判斷二叉樹(shù)是否是完全二叉樹(shù)
int BinaryTreeComplete(BTNode* root);

// 初始化隊(duì)列 
void QueueInit(Queue* q)
{
	assert(q);
	q->_front = q->_rear = NULL;
}
// 隊(duì)尾入隊(duì)列 
void QueuePush(Queue* q, QDataType data)
{
	assert(q);
	QNode *newnode = ((QNode*)malloc(sizeof(QNode)));
	newnode->_data = data;
	newnode->_next = NULL;
	if (q->_rear == NULL)
	{
		q->_front = q->_rear = newnode;
	}
	else
	{
		q->_rear->_next = newnode;
		//q->_rear = q->_rear->_next;
		q->_rear = newnode;
	}
}
// 隊(duì)頭出隊(duì)列 
void QueuePop(Queue* q)
{
	assert(q);
	assert(!QueueEmpty(q));
	if (q->_front == q->_rear)
	{
		free(q->_front);
		//free(q->_rear);
		q->_front = q->_rear = NULL;
	}
	else
	{
		QNode *cur = q->_front->_next;
		free(q->_front);
		q->_front = cur;
	}
}
// 獲取隊(duì)列頭部元素 
QDataType QueueFront(Queue* q)
{
	assert(q);
	assert(!QueueEmpty(q));
	return q->_front->_data;
}
// 獲取隊(duì)列隊(duì)尾元素 
QDataType QueueBack(Queue* q)
{
	assert(q);
	assert(!QueueEmpty(q));
	return q->_rear->_data;
}
// 獲取隊(duì)列中有效元素個(gè)數(shù) 
int QueueSize(Queue* q)
{
	assert(q);
	int size = 0;
	QNode* cur = q->_front;
	while (cur)
	{
		++size;
		cur = cur->_next;
	}
	return size;
}
// 檢測(cè)隊(duì)列是否為空，如果為空返回非零結(jié)果，如果非空返回0 
int QueueEmpty(Queue* q)
{
	assert(q);
	return q->_front == NULL ? 1 : 0;
}
// 銷(xiāo)毀隊(duì)列 
void QueueDestroy(Queue* q)
{
	assert(q);
	QNode *cur = q->_front;
	while (cur)
	{
		QNode *next = cur->_next;
		free(cur);
		cur = next;
	}
	q->_front = q->_rear = NULL;
}

BTNode* CreateBTNode(BTDataType x)
{
	BTNode *node = (BTNode*)malloc(sizeof(BTNode));
	node->_data = x;
	node->_left = NULL;
	node->_right = NULL;
	return node;
}


// 通過(guò)前序遍歷的數(shù)組"ABD##E#H##CF##G##"構(gòu)建二叉樹(shù)
BTNode* BinaryTreeCreate(BTDataType* a, int n, int* pi)
{
	if (a[*pi] == '#')
	{
		return NULL;
	}
	BTNode *node = (BTNode*)malloc(sizeof(BTNode));
	node->_data = a[*pi];
	++*pi;
	node->_left = BinaryTreeCreate(a, n, pi);
	++*pi;
	node->_right = BinaryTreeCreate(a, n, pi);
	return node;
}
// 二叉樹(shù)銷(xiāo)毀
void BinaryTreeDestory(BTNode** root)
{
	if (*root != NULL)
	{
		if ((*root)->_left) // 有左孩子
			BinaryTreeDestory(&(*root)->_left); // 銷(xiāo)毀左孩子子樹(shù)
		if ((*root)->_right) // 有右孩子
			BinaryTreeDestory(&(*root)->_right); // 銷(xiāo)毀右孩子子樹(shù)

		free(*root); // 釋放根結(jié)點(diǎn)
		*root = NULL; // 空指針賦NULL
	}
}
// 二叉樹(shù)節(jié)點(diǎn)個(gè)數(shù)
int BinaryTreeSize(BTNode* root)
{
	if (root == NULL)
	{
		return 0;
	}
	return BinaryTreeSize(root->_left) + BinaryTreeSize(root->_right) + 1;
}
// 二叉樹(shù)葉子節(jié)點(diǎn)個(gè)數(shù)
int BinaryTreeLeafSize(BTNode* root)
{
	if (root == NULL)
	{
		return 0;
	}
	if (root->_left == NULL&&root->_right == NULL)
	{
		return 1;
	}
	return BinaryTreeLeafSize(root->_left) + BinaryTreeLeafSize(root->_right);
}
// 二叉樹(shù)第k層節(jié)點(diǎn)個(gè)數(shù)
int BinaryTreeLevelKSize(BTNode* root, int k)
{
	if (root == NULL)
	{
		return 0;
	}
	if (k == 1)
	{
		return 1;
	}
	return BinaryTreeLevelKSize(root->_left, k - 1) + BinaryTreeLevelKSize(root->_right, k - 1);
}
// 二叉樹(shù)查找值為x的節(jié)點(diǎn)
BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
{
	if (root == NULL)
	{
		return NULL;
	}
	if (root->_data == x)
	{
		return root;
	}
	BTNode* ret=BinaryTreeFind(root->_left,x);
	if (ret != NULL)
	{
		return ret;
	}
	ret = BinaryTreeFind(root->_right, x);
	if (ret != NULL)
	{
		return ret;
	}
	return NULL;
}
// 二叉樹(shù)前序遍歷 
void BinaryTreePrevOrder(BTNode* root)
{
	if (root == NULL)
	{
		//printf("NULL  ");
		return;
	}
	printf("%c  ", root->_data);
	BinaryTreePrevOrder(root->_left);
	BinaryTreePrevOrder(root->_right);
}
// 二叉樹(shù)中序遍歷
void BinaryTreeInOrder(BTNode* root)
{
	if (root == NULL)
	{
		//printf("NULL  ");
		return;
	}
	BinaryTreeInOrder(root->_left);
	printf("%c  ", root->_data);
	BinaryTreeInOrder(root->_right);
}
// 二叉樹(shù)后序遍歷
void BinaryTreePostOrder(BTNode* root)
{
	if (root == NULL)
	{
		//printf("NULL  ");
		return;
	}
	BinaryTreePostOrder(root->_left);
	BinaryTreePostOrder(root->_right);
	printf("%c  ", root->_data);
}
// 層序遍歷
void BinaryTreeLevelOrder(BTNode* root)
{
	Queue q;
	QueueInit(&q);
	if (root)
	{
		QueuePush(&q, root);
	}
	while (!QueueEmpty(&q))
	{
		BTNode *front = QueueFront(&q);
		QueuePop(&q);
		printf("%c  ", front->_data);
		if (front->_left)
		{
			QueuePush(&q, front->_left);
		}
		if (front->_right)
		{
			QueuePush(&q, front->_right);
		}
	}
}
// 判斷二叉樹(shù)是否是完全二叉樹(shù)
int BinaryTreeComplete(BTNode* root)
{
	Queue q;
	QueueInit(&q);
	if (root)
	{
		QueuePush(&q, root);
	}
	while (!QueueEmpty(&q))
	{
		BTNode *front = QueueFront(&q);
		QueuePop(&q);
		if (front == NULL)
		{
			break;
		}
		printf("%s ", front->_data);
		if (front->_left)
		{
			QueuePush(&q, front->_left);
		}
		if (front->_right)
		{
			QueuePush(&q, front->_right);
		}
	}
	while (!QueueEmpty(&q))
	{
		BTNode *front = QueueFront(&q);
		QueuePop(&q);
		if (front != NULL)
		{
			return 0;
		}
	}
	return 1;
}

#include <stdio.h>  
#include <stdlib.h>  
#include <malloc.h>  
#define MAXSIZE 100  
typedef char ElemType;  
typedef enum  
{  
    Link,/*指向孩子結(jié)點(diǎn)*/Thread/*指向前驅(qū)或后繼*/  
} PointerTag;  
typedef struct Node  
{  
    ElemType data;  
    struct Node *lchild;  
    struct Node *rchild;  
    PointerTag ltag,rtag;  
}*BitThrTree,BitThrNode;  
  
BitThrTree pre;  
void CreateBitTree2(BitThrTree *T,char str[]);//創(chuàng)建搜索二叉樹(shù)  
void InThreading(BitThrTree p);//中序線索化二叉樹(shù)  
int InOrderThreading(BitThrTree *Thrt,BitThrTree T);//通過(guò)中序遍歷二叉樹(shù)T，使T中序線索化。Thrt是指向頭結(jié)點(diǎn)的指針  
int InOrderTraverse(BitThrTree T,int (*visit)(BitThrTree e));//中序遍歷線索二叉樹(shù)  
int Print(BitThrTree T);//打印二叉樹(shù)的結(jié)點(diǎn)和線索標(biāo)志  
BitThrNode* FindPoint(BitThrTree T,ElemType e);//在線索二叉樹(shù)中查找結(jié)點(diǎn)為e的指針  
BitThrNode* InOrderPre(BitThrNode *p);//中序前驅(qū)  
BitThrNode* InOrderPost(BitThrNode *p);//中序后繼  
void DestroyBitTree(BitThrTree *T);//銷(xiāo)毀二叉樹(shù)  
 
 
#include "LinkBiTree.h"  
  
void CreateBitTree2(BitThrTree *T,char str[])//創(chuàng)建搜索二叉樹(shù)  
{  
    char ch;  
    BitThrTree stack[MAXSIZE];  
    int top = -1;  
    int flag,k;  
    BitThrNode *p;  
    *T = NULL,k = 0;  
    ch = str[k];  
    while(ch != '\0')  
    {  
        switch(ch)  
        {  
        case '(':  
            stack[++top] = p;  
            flag = 1;  
            break;  
        case ')':  
            top--;  
            break;  
        case ',':  
            flag = 2;  
            break;  
        default:  
            p = (BitThrTree)malloc(sizeof(BitThrNode));  
            p->data = ch;  
            p->lchild = NULL;  
            p->rchild = NULL;  
            if(*T == NULL)  
            {  
                *T = p;  
            }  
            else  
            {  
                switch(flag)  
                {  
                case 1:  
                    stack[top]->lchild = p;  
                    break;  
                case 2:  
                    stack[top]->rchild = p;  
                    break;  
                }  
                if(stack[top]->lchild)  
                {  
                    stack[top]->ltag = Link;  
                }  
                if(stack[top]->rchild)  
                {  
                    stack[top]->rtag = Link;  
                }  
            }  
        }  
        ch = str[++k];  
    }  
}  
void InThreading(BitThrTree p)//中序線索化二叉樹(shù)  
{  
    if(p)//左子樹(shù)線索化  
    {  
        InThreading(p->lchild);  
        if(!p->lchild)//前驅(qū)線索化  
        {  
            p->ltag = Thread;  
            p->lchild = pre;  
        }  
        if(!pre->rchild)//后繼線索化  
        {  
            pre->rtag = Thread;  
            pre->rchild = p;  
        }  
        pre = p;  
        InThreading(p->rchild);//右子樹(shù)線索化  
    }  
}  
int InOrderThreading(BitThrTree *Thrt,BitThrTree T)//通過(guò)中序遍歷二叉樹(shù)T，使T中序線索化。Thrt是指向頭結(jié)點(diǎn)的指針  
{  
    if(!(*Thrt = (BitThrTree)malloc(sizeof(BitThrNode))))  
    {  
        exit(-1);//為頭結(jié)點(diǎn)分配單元  
    }  
    (*Thrt)->ltag = Link;//修改前驅(qū)線索標(biāo)志  
    (*Thrt)->rtag = Thread;//修改后繼線索標(biāo)志  
    (*Thrt)->rchild = *Thrt;//將頭結(jié)點(diǎn)的rchild指針指向自己  
    if(!T)//如果二叉樹(shù)為空，則將lchild指針指向自己  
    {  
        (*Thrt)->lchild = *Thrt;  
    }  
    else  
    {  
        (*Thrt)->lchild = T;//將頭結(jié)點(diǎn)的左指針指向根結(jié)點(diǎn)  
        pre = *Thrt;//將pre指向已經(jīng)線索化的結(jié)點(diǎn)  
        InThreading(T);//中序遍歷進(jìn)行中序線索化  
        /*將最后一個(gè)結(jié)點(diǎn)線索化*/  
        pre->rchild = *Thrt;//將最后一個(gè)結(jié)點(diǎn)的右指針指向頭結(jié)點(diǎn)  
        pre->rtag  = Thread;//修改最后一個(gè)結(jié)點(diǎn)的rtag標(biāo)志域  
        (*Thrt)->rchild = pre;//將頭結(jié)點(diǎn)的rchild指針指向最后一個(gè)結(jié)點(diǎn)  
    }  
    return 1;  
}  
int InOrderTraverse(BitThrTree T,int (*visit)(BitThrTree e))//中序遍歷線索二叉樹(shù)  
{  
    BitThrTree p;  
    p = T->lchild ;//p指向根結(jié)點(diǎn)  
    while(p != T)//空樹(shù)或遍歷結(jié)束時(shí)，p == T  
    {  
        while(p->ltag == Link)  
        {  
            p = p->lchild ;  
        }  
        if(!visit(p))//打印  
        {  
            return 0;  
        }  
        while(p->rtag == Thread && p->rchild != T)//訪問(wèn)后繼結(jié)點(diǎn)  
        {  
            p = p->rchild ;  
            visit(p);  
        }  
        p = p->rchild ;  
    }  
    return 1;  
}  
int Print(BitThrTree T)//打印二叉樹(shù)的結(jié)點(diǎn)和線索標(biāo)志  
{  
    static int k = 1;  
    printf("%2d\t%s\t %2c\t %s\t\n",k++,T->ltag == 0 ? "Link":"Thread",T->data ,T->rtag == 1 ? "Thread":"Link");  
    return 1;  
}  
BitThrNode* FindPoint(BitThrTree T,ElemType e)//在線索二叉樹(shù)中查找結(jié)點(diǎn)為e的指針  
{  
    BitThrTree p;  
    p = T->lchild ;  
    while(p != T)  
    {  
        while(p->ltag == Link)  
        {  
            p = p->lchild ;  
        }  
        if(p->data == e)  
        {  
            return p;  
        }  
        while(p->rtag == Thread && p->rchild != T)  
        {  
            p = p->rchild ;  
            if(p->data == e)  
            {  
                return p;  
            }  
        }  
        p = p->rchild ;  
    }  
    return NULL;  
}  
BitThrNode* InOrderPre(BitThrNode *p)//中序前驅(qū)  
{  
    if(p->ltag == Thread)//如果p的標(biāo)志域ltag為線索，則p的左子樹(shù)結(jié)點(diǎn)為前驅(qū)  
    {  
        return p->lchild ;  
    }  
    else  
    {  
        pre = p->lchild ;//查找p的左孩子的最右下端結(jié)點(diǎn)  
        while(pre->rtag == Link)//右子樹(shù)非空時(shí)，沿右鏈往下查找  
        {  
            pre = pre->rchild ;  
        }  
        return pre;//pre就是最右下端結(jié)點(diǎn)  
    }  
}  
BitThrNode* InOrderPost(BitThrNode *p)//中序后繼  
{  
    if(p->rtag == Thread)//如果p的標(biāo)志域rtag為線索，則p的右子樹(shù)結(jié)點(diǎn)為后驅(qū)  
    {  
        return p->rchild ;  
    }  
    else  
    {  
        pre = p->rchild ;//查找p的右孩子的最左下端結(jié)點(diǎn)  
        while(pre->ltag == Link)//左子樹(shù)非空時(shí)，沿左鏈往下查找  
        {  
            pre = pre->lchild ;  
        }  
        return pre;//pre就是最左下端結(jié)點(diǎn)  
    }  
}  
void DestroyBitTree(BitThrTree *T)//銷(xiāo)毀二叉樹(shù)  
{  
    if(*T)  
    {  
        if(!(*T)->lchild)  
        {  
            DestroyBitTree(&((*T)->lchild));  
        }  
        if(!(*T)->rchild)  
        {  
            DestroyBitTree(&((*T)->rchild));  
        }  
        free(*T);  
        *T = NULL;  
    }  
}  
 
 
#include "LinkBiTree.h"  
  
int main(void)  
{  
    BitThrTree T,Thrt;  
    BitThrNode *p,*pre,*post;  
    CreateBitTree2(&T,"(A(B(,D(G)),C(E(,H),F)))");  
    printf("線索二叉樹(shù)的輸出序列：\n");  
    InOrderThreading(&Thrt,T);  
    printf("序列  前驅(qū)標(biāo)志  結(jié)點(diǎn)  后繼標(biāo)志\n");  
    InOrderTraverse(Thrt,Print);  
    p = FindPoint(Thrt,'D');  
    pre = InOrderPre(p);  
    printf("元素D的中序直接前驅(qū)元素是：%c\n",pre->data);  
    post = InOrderPost(p);  
    printf("元素D的中序直接后驅(qū)元素是：%c\n",post->data);  
    p = FindPoint(Thrt,'E');  
    pre = InOrderPre(p);  
    printf("元素E的中序直接前驅(qū)元素是：%c\n",pre->data);  
    post = InOrderPost(p);  
    printf("元素E的中序直接后驅(qū)元素是：%c\n",post->data);  
    DestroyBitTree(&Thrt);  
    return 0;  
}  

#include <iostream>
#include <cstdio>
#include <vector>
using namespace std;

#define MAXL 100010

int N, M, A[MAXL];
vector<int> G[MAXL]; //vector存圖 

void dfs(int x, int d) {
	if(A[x]) return; //訪問(wèn)過(guò) 
	A[x] = d;
	for(int i=0; i<G[x].size(); i++)
		dfs(G[x][i], d);
}

int main() {
	int u, v;
	scanf("%d%d", &N, &M);
	for(int i=1; i<=M; i++) {
		scanf("%d%d", &u, &v);
		G[v].push_back(u); //反向建邊 
	}
	for(int i=N; i; i--) dfs(i, i); 
	for(int i=1; i<=N; i++) printf("%d ", A[i]);
	printf("\n");
	return 0;
}

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<queue>
using namespace std;
const int Len = 200 * 200 * 5 + 5,Inf = 1e9;
int dep[Len],cnt = 1,head[Len],s,t,S,T,cur[Len],val[Len],a[205][205],sumh[205],suml[205],LL,RR,n,m,sum,ans,minn;
struct node
{
	int next,to,w;
}edge[Len << 1];
void add(int from,int to,int w)
{
	edge[++ cnt].to = to;
	edge[cnt].w = w;
	edge[cnt].next = head[from];
	head[from] = cnt;
}
int BFS()
{
	queue<int> q;
	memset(dep , 0 , sizeof dep);
	q.push(S);dep[S] = 1;cur[S] = head[S];
	while(!q.empty())
	{
		int p = q.front() ; q.pop();
		for(int e = head[p] ; e ; e = edge[e].next)
		{
			int to = edge[e].to;
			if(!dep[to] && edge[e].w)
			{
				dep[to] = dep[p] + 1;
				cur[to] = head[to];
				if(T == to) return dep[T];
				q.push(to);
			}
		}
	}
	return dep[T];
}
int dfs(int u,int In)
{
	if(u == T) return In;
	int Out = 0;
	for(int e = cur[u] ; e && In > 0 ; e = edge[e].next)
	{
		cur[u] = e;
		int to = edge[e].to;
		if(edge[e].w && dep[to] == dep[u] + 1)
		{
			int res = dfs(to , min(In , edge[e].w));
			In -= res;
			Out += res;
			edge[e].w -= res;
			edge[e ^ 1].w += res; 
		}
	}
	return (!Out) ? dep[u] = 0 : Out;
}
int Clone(int x,int y){return (x - 1) * n + y;}
bool check(int res)
{
	memset(head , 0 , sizeof head) ; cnt = 1;
	memset(val , 0 , sizeof val);
	sum = ans = 0;
	for(int i = 1 ; i < n ; i ++)//處理行
	{
		int now = Clone(i , m) , L = sumh[i] - res , R = sumh[i] + res;//L = sumh[i] - res , R = sumh[i] + res
		add(s , now , R - L) , add(now , s , 0);
		val[now] += L , val[s] -= L;
	}
	for(int i = 1 ; i < m ; i ++)
	{
		int now = Clone(n , i) , L = suml[i] - res , R = suml[i] + res;
		add(now , s , R - L) , add(s , now , 0);
		val[s] += L , val[now] -= L; 
	}
	for(int i = 1 ; i < n ; i ++)
	{
		int now = Clone(i , m);
		for(int j = 1 ; j < m ; j ++)
		{
			int to = Clone(i , j);
			add(now , to , RR - LL) , add(to , now , 0);
			val[to] += LL , val[now] -= LL; 
		}
	} 
	for(int i = 1 ; i < m ; i ++)
	{
		int now = Clone(n , i);
		for(int j = 1 ; j < n ; j ++)
		{
			int to = Clone(j , i);
			add(to , now , RR - LL) , add(now , to , 0);
			val[now] += LL , val[to] -= LL;
		}
	}
	for(int i = 1 ; i <= n * m + 1 ; i ++)
	{
		if(val[i] > 0) add(S , i , val[i]) , add(i , S , 0) , sum += val[i];
		if(val[i] < 0) add(i , T , -val[i]) , add(T , i , 0);
	}
	while(BFS()) ans += dfs(S , Inf);
	if(ans == sum) return true;
	return false;
}
signed main()
{
	minn = 1e9;
	scanf("%d %d",&n,&m);
	n ++ , m ++;
	s = n * m , t = n * m + 1 , S = n * m + 2 , T = n * m + 3; 
	for(int i = 1 ; i <= n - 1 ; i ++)
		for(int j = 1 ; j <= m - 1 ; j ++) 
		{
			scanf("%d",&a[i][j]);
			sumh[i] += a[i][j] , suml[j] += a[i][j];
		}
	for(int i = 1 ; i <= n - 1 ; i ++) minn = min(minn , sumh[i]);
	for(int i = 1 ; i <= m - 1 ; i ++) minn = min(minn , suml[i]);
	scanf("%d %d",&LL,&RR);
	int l = 0 , r = minn,anss;
	while(l <= r)
	{
		int mid = (l + r) >> 1;
		if(check(mid)) anss = mid , r = mid - 1;
		else l = mid + 1; 
	}
	printf("%d\n",anss);
	return 0;
}

#include <iostream>
#include <cstdio>
#include <vector>
using namespace std;

#define MAXL 100010

int N, M, A[MAXL];
vector<int> G[MAXL]; //vector存圖 

void dfs(int x, int d) {
	if(A[x]) return; //訪問(wèn)過(guò) 
	A[x] = d;
	for(int i=0; i<G[x].size(); i++)
		dfs(G[x][i], d);
}

int main() {
	int u, v;
	scanf("%d%d", &N, &M);
	for(int i=1; i<=M; i++) {
		scanf("%d%d", &u, &v);
		G[v].push_back(u); //反向建邊 
	}
	for(int i=N; i; i--) dfs(i, i); 
	for(int i=1; i<=N; i++) printf("%d ", A[i]);
	printf("\n");
	return 0;
}

#include<iostream>//P1443
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<queue>//運(yùn)用了隊(duì)列
#include<cmath>
using namespace std;
const int dx[8]={-1,-2,-2,-1,1,2,2,1};
const int dy[8]={2,1,-1,-2,2,1,-1,-2};//8個(gè)方向
queue<pair<int,int> > q;
int f[500][500];//存步數(shù)
bool vis[500][500];//走沒(méi)走過(guò)
int main()
{
	int n,m,x,y;
	memset(f,-1,sizeof(f));memset(vis,false,sizeof(vis));
	cin>>n>>m>>x>>y;
	f[x][y]=0;vis[x][y]=true;q.push(make_pair(x,y));
	while(!q.empty())
	{
		int xx=q.front().first,yy=q.front().second;q.pop();//取隊(duì)首并出隊(duì)
		for(int i=0;i<8;i++)
		{
			int u=xx+dx[i],v=yy+dy[i];
			if(u<1||u>n||v<1||v>m||vis[u][v])continue;//出界或走過(guò)就不走
		    vis[u][v]=true;q.push(make_pair(u,v));f[u][v]=f[xx][yy]+1;
		}
	}
	for(int i=1;i<=n;i++)
	 {for(int j=1;j<=m;j++)printf("%-5d",f[i][j]);printf("\n");}//注意場(chǎng)寬?。?
	return 0;
}

#pragma once
#include<iostream>
#include<string>
using namespace std;

//鄰接矩陣保存
//記錄起點(diǎn)到每個(gè)頂點(diǎn)的最短路徑的信息
struct Dis {
    string path;
    int value;
    bool visit;
    Dis() {
        visit = false;
        value = 0;
        path = "";
    }
};

class Graph_DG {
private:
    int vexnum;   //圖的頂點(diǎn)個(gè)數(shù)
    int edge;     //圖的邊數(shù)
    int **arc;   //鄰接矩陣
    Dis * dis;   //記錄各個(gè)頂點(diǎn)最短路徑的信息
public:
    //構(gòu)造函數(shù)
    Graph_DG(int vexnum, int edge);
    //析構(gòu)函數(shù)
    ~Graph_DG();
    // 判斷我們每次輸入的的邊的信息是否合法
    //頂點(diǎn)從1開(kāi)始編號(hào)
    bool check_edge_value(int start, int end, int weight);
    //創(chuàng)建圖
    void createGraph();
    //打印鄰接矩陣
    void print();
    //求最短路徑
    void Dijkstra(int begin);
    //打印最短路徑
    void print_path(int);
};

#include"Dijkstra.h"

//構(gòu)造函數(shù)
Graph_DG::Graph_DG(int vexnum, int edge) {
    //初始化頂點(diǎn)數(shù)和邊數(shù)
    this->vexnum = vexnum;
    this->edge = edge;
    //為鄰接矩陣開(kāi)辟空間和賦初值
    arc = new int*[this->vexnum];
    dis = new Dis[this->vexnum];
    for (int i = 0; i < this->vexnum; i++) {
        arc[i] = new int[this->vexnum];
        for (int k = 0; k < this->vexnum; k++) {
            //鄰接矩陣初始化為無(wú)窮大
                arc[i][k] = INT_MAX;
        }
    }
}
//析構(gòu)函數(shù)
Graph_DG::~Graph_DG() {
    delete[] dis;
    for (int i = 0; i < this->vexnum; i++) {
        delete this->arc[i];
    }
    delete arc;
}

// 判斷我們每次輸入的的邊的信息是否合法
//頂點(diǎn)從1開(kāi)始編號(hào)
bool Graph_DG::check_edge_value(int start, int end, int weight) {
    if (start<1 || end<1 || start>vexnum || end>vexnum || weight < 0) {
        return false;
    }
    return true;
}

void Graph_DG::createGraph() {
    cout << "請(qǐng)輸入每條邊的起點(diǎn)和終點(diǎn)（頂點(diǎn)編號(hào)從1開(kāi)始）以及其權(quán)重" << endl;
    int start;
    int end;
    int weight;
    int count = 0;
    while (count != this->edge) {
        cin >> start >> end >> weight;
        //首先判斷邊的信息是否合法
        while (!this->check_edge_value(start, end, weight)) {
            cout << "輸入的邊的信息不合法，請(qǐng)重新輸入" << endl;
            cin >> start >> end >> weight;
        }
        //對(duì)鄰接矩陣對(duì)應(yīng)上的點(diǎn)賦值
        arc[start - 1][end - 1] = weight;
        //無(wú)向圖添加上這行代碼
        //arc[end - 1][start - 1] = weight;
        ++count;
    }
}

void Graph_DG::print() {
    cout << "圖的鄰接矩陣為：" << endl;
    int count_row = 0; //打印行的標(biāo)簽
    int count_col = 0; //打印列的標(biāo)簽
    //開(kāi)始打印
    while (count_row != this->vexnum) {
        count_col = 0;
        while (count_col != this->vexnum) {
            if (arc[count_row][count_col] == INT_MAX)
                cout << "∞" << " ";
            else
            cout << arc[count_row][count_col] << " ";
            ++count_col;
        }
        cout << endl;
        ++count_row;
    }
}
void Graph_DG::Dijkstra(int begin){
    //首先初始化我們的dis數(shù)組
    int i;
    for (i = 0; i < this->vexnum; i++) {
        //設(shè)置當(dāng)前的路徑
        dis[i].path = "v" + to_string(begin) + "-->v" + to_string(i + 1);
        dis[i].value = arc[begin - 1][i];
    }
    //設(shè)置起點(diǎn)的到起點(diǎn)的路徑為0
    dis[begin - 1].value = 0;
    dis[begin - 1].visit = true;

    int count = 1;
    //計(jì)算剩余的頂點(diǎn)的最短路徑（剩余this->vexnum-1個(gè)頂點(diǎn)）
    while (count != this->vexnum) {
        //temp用于保存當(dāng)前dis數(shù)組中最小的那個(gè)下標(biāo)
        //min記錄的當(dāng)前的最小值
        int temp=0;
        int min = INT_MAX;
        for (i = 0; i < this->vexnum; i++) {
            if (!dis[i].visit && dis[i].value<min) {
                min = dis[i].value;
                temp = i;
            }
        }
        //cout << temp + 1 << "  "<<min << endl;
        //把temp對(duì)應(yīng)的頂點(diǎn)加入到已經(jīng)找到的最短路徑的集合中
        dis[temp].visit = true;
        ++count;
        for (i = 0; i < this->vexnum; i++) {
            //注意這里的條件arc[temp][i]!=INT_MAX必須加，不然會(huì)出現(xiàn)溢出，從而造成程序異常
            if (!dis[i].visit && arc[temp][i]!=INT_MAX && (dis[temp].value + arc[temp][i]) < dis[i].value) {
                //如果新得到的邊可以影響其他為訪問(wèn)的頂點(diǎn)，那就就更新它的最短路徑和長(zhǎng)度
                dis[i].value = dis[temp].value + arc[temp][i];
                dis[i].path = dis[temp].path + "-->v" + to_string(i + 1);
            }
        }
    }

}
void Graph_DG::print_path(int begin) {
    string str;
    str = "v" + to_string(begin);
    cout << "以"<<str<<"為起點(diǎn)的圖的最短路徑為：" << endl;
    for (int i = 0; i != this->vexnum; i++) {
        if(dis[i].value!=INT_MAX)
        cout << dis[i].path << "=" << dis[i].value << endl;
        else {
            cout << dis[i].path << "是無(wú)最短路徑的" << endl;
        }
    }
}

#include"Dijkstra.h"

//檢驗(yàn)輸入邊數(shù)和頂點(diǎn)數(shù)的值是否有效，可以自己推算為啥：
//頂點(diǎn)數(shù)和邊數(shù)的關(guān)系是：((Vexnum*(Vexnum - 1)) / 2) < edge
bool check(int Vexnum, int edge) {
    if (Vexnum <= 0 || edge <= 0 || ((Vexnum*(Vexnum - 1)) / 2) < edge)
        return false;
    return true;
}
int main() {
    int vexnum; int edge;

    cout << "輸入圖的頂點(diǎn)個(gè)數(shù)和邊的條數(shù)：" << endl;
    cin >> vexnum >> edge;
    while (!check(vexnum, edge)) {
        cout << "輸入的數(shù)值不合法，請(qǐng)重新輸入" << endl;
        cin >> vexnum >> edge;
    }
    Graph_DG graph(vexnum, edge);
    graph.createGraph();
    graph.print();
    graph.Dijkstra(1);
    graph.print_path(1);
    system("pause");
    return 0;
}

//總體上是一個(gè)二重循環(huán)加上一個(gè)三重循環(huán)，主要運(yùn)用于所有頂點(diǎn)到所有頂點(diǎn)的最短路徑問(wèn)題
void ShortestPath FLOYD(MGraph G, PathMatrix &p[], DistanceMatrix &D){
	//用Floyd算法求有向網(wǎng)中各對(duì)頂點(diǎn)v和w之間的最短路徑P[v][w]及其帶權(quán)長(zhǎng)
	//度D[v][w].若P[v][w][u]為T(mén)RUE,則u是從v到w當(dāng)前求得最短路徑上的頂點(diǎn)。
	for(v = 0; v < G.vexnum; ++v)		//各對(duì)結(jié)點(diǎn)之間初始已知路徑及距離
		for(w = 0; w < G.vexnum; ++w){
			D[v][w] = G.arcs[v][w];
			for(u = 0; u < G.vexnum; ++w)	P[v][w][u] = FALSE;
			if(D[v][w] < INFINITY){				//從v到w有直接路徑
				P[v][w][v] = TRUE; P[v][w][w] = TRUE;
			}//if
		}//for
	
	for(u = 0; u < G.vexnum; ++u)
		for(v = 0; v<G.vexnum; ++v)
			for(w = 0; w<G.vexnum; ++w)
				if(D[v][u] + D[u][w] < D[v][w]){		//從v經(jīng)u到w的一條路徑更短
					D[v][w] = D[v][u] + D[u][w];
					for(i = 0; i<G.vexnum; ++i)
						P[v][w][i] = P[v][u][i] || P[u][w][i];
						}//if
}//ShortestPath.FLOYD