#include <iostream>

using namespace std;

void heapSort(int A[], int len);
void buildHeap(int A[], int len);
void adjust(int A[], int i, int max);
void swap(int * a, int * b);

int main(){
	int A[7] = {1,3,4,2,7,5,6};
	heapSort(A, 7);
	for(int i = 0; i <= 6; i++){
		cout << A[i] << " ";
	}
}

void heapSort(int A[], int len){
	buildHeap(A,len);
	for(int i = len-1; i >= 0; i--){
		swap(&A[0], &A[i]);
		adjust(A, 1, i);
	}
}

void buildHeap(int A[], int len){
	for(int i = len/2; i >= 1; i--){
		adjust(A, i, len);
	}
}

void adjust(int A[], int i, int max){
	int left = 2 * i;
	int right = 2 * i + 1;
	int maxIndex = i;
	if(left <= max&&A[maxIndex-1] < A[left-1]){
		maxIndex = left;
	}
	if(right <= max&&A[maxIndex-1] < A[right-1]){
		maxIndex = right;
	}
	if(maxIndex != i){
		swap(&A[maxIndex-1], &A[i-1]);
		adjust(A, maxIndex, max);
	}
}

void swap(int * a, int * b){
	if(*a != *b){
		*a ^= *b;
 		*b ^= *a;
 		*a ^= *b;
	}
}

void preOrderTraversalNonRecursive(TreeNode * root){
	stack<TreeNode*> stk;
	for(;;){
		while(root != NULL){
			cout << root->val << " ";//visit
			stk.push(root);
			root = root->left;
		}
		if(!stk.empty()){
			root = stk.top();
			root = root->right;
			stk.pop();
		}else{
			return;
		}
	}
}

void inOrderTraversalNonRecursive(TreeNode * root){
	stack<TreeNode*> stk;
	for(;;){
		while(root != NULL){
			stk.push(root);
			root = root->left;
		}
		if(!stk.empty()){
			root = stk.top();
			stk.pop();
			cout << root->val << " ";//visit
			root = root->right;
		}else{
			return;
		}
	}
}

void postOrderTraversalNonRecursive(TreeNode * root){
	stack<TreeNode*> stk;
	TreeNode * lastVisit = NULL;
	for(;;){
		while(root != NULL){
			stk.push(root);
			root = root->left;
		}
		while(!stk.empty()){
			root = stk.top();
			if(root->right == lastVisit || root->right == NULL){
				cout << root->val << " ";//visit
				lastVisit = root;
				stk.pop();
			}else{
				root = root->right;//root can't be NULL here
				break;
			}
		}
		if(stk.empty()) return;
	}
}

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

int kmp_find(const string& target, const string& pattern) {
    const int target_length = target.size();
    const int pattern_length = pattern.size();
    int * overlay_value = new int[pattern_length];
    overlay_value[0] = -1;
    int index = 0;
    for (int i = 1; i < pattern_length; ++i) {
        index = overlay_value[i - 1];
        while (index >= 0 && pattern[index + 1] != pattern[i]) {
            index = overlay_value[index];
        }
        if (pattern[index + 1] == pattern[i]) {
            overlay_value[i] = index + 1;
        } else {
            overlay_value[i] = -1;
        }
    }
    //match algorithm start
    int pattern_index = 0;
    int target_index = 0;
    while (pattern_index < pattern_length && target_index < target_length) {
        if (target[target_index] == pattern[pattern_index]) {
            ++target_index;
            ++pattern_index;
        } else if (pattern_index == 0) {
            ++target_index;
        } else {
            pattern_index = overlay_value[pattern_index - 1] + 1;
        }
    }
    if (pattern_index == pattern_length) {
        return target_index - pattern_index;
    } else {
        return -1;
    }
    delete [] overlay_value;
}

int main() {
    string source = " annbcdanacadsannannabnna";
    string pattern = " annacanna";
    cout << kmp_find(source, pattern) << endl;
    return 0;
}

#include <iostream>

using namespace std;

class ListNode{
public:

	int val;
	ListNode * next;
	ListNode(int _val):val(_val),next(NULL){}
};

ListNode * quickSort(ListNode * head){
	if(head == NULL || head->next == NULL){
		return head;
	}
	ListNode dummyFront(-1), dummyMid(-1), dummyBack(-1);
	ListNode * frontTail = NULL, * midTail = NULL, * backTail = NULL;
	int num = head->val;
	for(ListNode * itr = head; itr != NULL; itr = itr->next){
		if(itr->val == num){
			if(midTail == NULL){
				dummyMid.next = itr;
				midTail = itr;
			}else{
				midTail->next = itr;
				midTail = midTail->next;
			}
		}else if(itr->val < num){
			if(frontTail == NULL){
				dummyFront.next = itr;
				frontTail = itr;
			}else{
				frontTail->next = itr;
				frontTail = frontTail->next;
			}
		}else{
			if(backTail == NULL){
				dummyBack.next = itr;
				backTail = itr;
			}else{
				backTail->next = itr;
				backTail = backTail->next;
			}
		}
	}
	if(frontTail != NULL) frontTail->next = NULL;
	if(midTail != NULL) midTail->next = NULL;
	if(backTail != NULL) backTail->next = NULL;
	ListNode * frontRet = quickSort(dummyFront.next);
	ListNode * backRet = quickSort(dummyBack.next);
	ListNode * ret = frontRet == NULL ?dummyMid.next:frontRet;
	if(frontRet != NULL){
		ListNode * itr = NULL;
		for(itr = frontRet; itr->next != NULL; itr = itr->next){}
		itr->next = dummyMid.next;
	}
	midTail->next = backRet;
	return ret;
}

 #include <iostream>
 #include <stdio.h>
 #include <string.h>
 #include <stack>
 using namespace std;
 //toposort的三种情况
 const int N=27;
 int n,m;
 int graph[N][N],indegree[N],list[N];
 
 int toposort(int n)
 {
     int in[N];
     memcpy(in,indegree,sizeof(indegree)); //复制入度数组，以免对主函数中的indegree有影响
     stack<int> s;
     int i;
     for(i=0;i<n;i++)
         if(!in[i])
             s.push(i);//所有入度为0的点入栈，如果这些点多于1的话，序列不确定
     int flag=0;
     int t,j=0;
     while(!s.empty())
     {
         if(s.size()>1)
             flag=1;    //序列不确定
         t=s.top();
         s.pop();
         list[j++]=t;   //记录出栈的数字
         for(i=0;i<n;i++)
             if(graph[t][i])
                 if(--in[i]==0)
                     s.push(i);//入度为0的点入栈
     }
     if(j!=n)//不能拓扑排序，即有环
         return 1;
     else if(flag==1)//有多种排序方式，不能唯一确定
         return 2;
     return 0;//序列能够被唯一确定
 }
 
 int main()
 {
     int determined,inconsistency;
     int i,j,res;
     char a,b;
     while(scanf("%d%d",&n,&m) && n!=0 && m!=0)
     {
         getchar();
         determined=0;
         inconsistency=0;
         memset(graph,0,sizeof(graph));
         memset(indegree,0,sizeof(indegree));
         for(i=1;i<=m;i++)
         {
             scanf("%c<%c",&a,&b);
             getchar();
             if(!determined && !inconsistency)
             {
                 if(graph[b-'A'][a-'A']==1)//存在反向边，则发现矛盾
                 {
                     inconsistency=1;
                     printf("Inconsistency found after %d relations.\n",i);
                     continue;
                 }
                 if(graph[a-'A'][b-'A']==0)
                 {
                     graph[a-'A'][b-'A']=1;
                     indegree[b-'A']++;
                 }
                 res=toposort(n);//toposort
                 if(res==0)//序列能够被唯一确定
                 {
                     printf("Sorted sequence determined after %d relations: ",i);
                     for(j=0;j<n;j++)
                         printf("%c",list[j]+'A');
                     printf(".\n");
                     determined=1;
                 }
                 else if(res==1)//不能拓扑排序，即有环，发现矛盾
                 {
                     printf("Inconsistency found after %d relations.\n",i);
                     inconsistency=1;
                 }
             }
 
         }
         if(!determined && !inconsistency)//既没有唯一确定，也没发现矛盾（有环），即不能确定
             printf("Sorted sequence cannot be determined.\n");
     }
     return 0;
 }

#include<iostream>
using namespace std;
int times=1,low[1000],dfn[1000];

int stack[1000],top=0;

bool instack[1000]={false};

struct LIST
{
    int v;
    LIST *next;
};

LIST *head[1000]={NULL};

int min(int a,int b)
{
    if(a<b)
        return a;
    return b;
}


void tarjan(int v)      /*tarjan求强连通分支*/
{
    dfn[v]=low[v]=times++;      /*标记点v的DFS遍历序号*/
    stack[top++]=v;             /*将点v入栈*/
    instack[v]=true;            /*标记点v已经在栈中*/
    for(LIST *p=head[v];p!=NULL;p=p->next)      /*遍历V能直接到达的点*/
        if(!dfn[p->v])  /*如果v的邻接点没有入过栈*/
        {
            tarjan(p->v);
            low[v]=min(low[v],low[p->v]);   /*如果v能直接到达的这个点没在栈中,v的最早祖先为他们中的较小值*/
        }
        else if(instack[p->v])  /*如果在栈中*/
            low[v]=min(low[v],dfn[p->v]);   /*如果在栈中，则v的最早祖先是他的序号和那个点的序号较小的*/

    if(dfn[v]==low[v])      /*如果dfn[v]和low[v]相等，则说明v点是其所属强连通分支DFS遍历起点，这个强连通分支说有点都在v点之上*/
    {
        cout<<"{ ";
        do
        {
            v=stack[--top];
            instack[v]=false;
            cout<<v<<' ';
        }while(dfn[v]!=low[v]);
        cout<<"}"<<endl;        
    }
}


int main()
{
    int i,j,n,m;
    cin>>n;

    memset(dfn,0,sizeof(char)*4000);
    for(i=1;i<=n;i++)
    {   
        cout<<i<<"的邻接点数量:";
        cin>>m;
        cout<<"输入每个邻接点编号";
        LIST *rear=head[i];
        for(j=0;j<m;j++)        /*创建邻接表*/
        {
            if(!j)
            {
                rear=new LIST;
                head[i]=rear;
            }
            else
            {
                rear->next=new LIST;
                rear=rear->next;
            }
            rear->next=NULL;
            cin>>rear->v;
        }
    }
    
    for(i=1;i<=n;i++)
        if(!dfn[i])     /*如果i没有入过栈*/
            tarjan(i);

    system("pause");
    return 0;
}