dongtaigh.cpp

该算法主要是为了在图中找到强连通分支

#include <iostream.h>
class point
{
public:
	int y;
	int x;
	int h;
	point(){
		y=x=h=0;
	}
};
class skee
{
public:
	int map[100][100];		//地图
	int visited[100][100];  //存放已经找过的点的数据
	point points[10000];    //按从小到大存放点
	int point_index;
	int R;
	int C;
	int L;		//最大值
	void init(){
		point_index=0;
		L=1;
		cin>>R;
		cin>>C;
		for(int j=0;j<R;j++){
			for(int i=0;i<C;i++){
				cin>>map[j][i];
				visited[j][i]=-1;
				insert_point(map[j][i],j,i);
			}
		}
	}
	void insert_point(int h,int j,int i){	//插入排序
		for(int i1=0;i1<point_index;i1++){
			if(points[i1].h>=h){
				for(int j1=point_index;j1>=i1;j1--){
					points[j1]=points[j1-1];
				}
				points[i1].h=h;
				points[i1].y=j;
				points[i1].x=i;
				point_index++;
				return;
			}
		}
		points[point_index].h=h;
		points[point_index].y=j;
		points[point_index].x=i;
		point_index++;
	}
	void skee_start(){
		for(int i=0;i<point_index;i++){
			Go(points[i].y,points[i].x,1);	
		}
	}
	int Go(int j,int i,int k){	//找每点的最大长度
		if(visited[j][i]!=-1){
			return visited[j][i];
		}
		int my=1;
		int t1(0),t2(0),t3(0),t4(0);
		bool tag=true;
		if(map[j+1][i]<map[j][i]&&j+1<R){
			t1 = Go(j+1,i,1);
			tag=false;
		}
		if(map[j-1][i]<map[j][i]&&j-1>=0){
			t2 = Go(j-1,i,1);
			tag=false;
		}
		if(map[j][i+1]<map[j][i]&&i+1<C){
			t3 = Go(j,i+1,1);
			tag=false;
		}
		if(map[j][i-1]<map[j][i]&&i-1>=0){
			t4 = Go(j,i-1,1);
			tag=false;
		}
		if(tag){
			if(L>1)
				L=1;
			visited[j][i]=1;
			return 1;
		}else{
			int max = t1>t2?t1:t2;
			max = max>t3?max:t3;
			max = max>t4?max:t4;
			my+=max;
			if(L<my){
				L=my;
			}
			visited[j][i] = my;
			return my;
		}
	}
	void display(){
		cout<<L<<endl;
	}
};
void main(){
	skee d;
	d.init();
	d.skee_start();
	d.display();
}