好离线最小值601offmin.cpp

设计一个算法

#include<iostream.h>
#include<fstream.h>
//using namespace std;
#include<string>
ifstream in("input.txt");
ofstream out("output.txt");
#include"time.h"
clock_t start,finish;

class UnionFind
{
public:
	UnionFind(int n);
	~UnionFind() {delete[] parent;delete [] root;}
	int Find(int e);
	void Union(int i,int j);
//private:
	int *parent;
	bool *root;
};

UnionFind::UnionFind(int n)
{
	root=new bool[n+1];
	parent=new int[n+1];
	for(int e=1;e<=n;e++)
	{
		parent[e]=1;
		root[e]=true;
	}
}

int UnionFind::Find(int e)
{
	int j=e;
	while(!root[j])
		j=parent[j];
	int f=e;
	while(f!=j)
	{
		int pf=parent[f];
		parent[f]=j;
		f=pf;
	}
	return j;
}

void UnionFind::Union(int i,int j)
{
	if(parent[i]<parent[j])
	{
		parent[j]+=parent[i];
		root[i]=false;
		parent[i]=j;
	}
	else
	{
		parent[i]+=parent[j];
		root[j]=false;
		parent[j]=i;
	}
}

void main()
{
	start=clock();
	if(in.fail())
	{
		cout<<"the input.txt is not exist!";
		exit(1);
	}
	int n,m,x,i,A,B;
    in>>n>>m;
    UnionFind UF(n);
	int *si=new int[n+2];
	int *is=new int[m+2];
//	for(i=0;i<m+2;i++)
//		is[i]=0;
	is[m+1]=0;
	int *prev=new int[m+2];
	int *next=new int[m+2];
	int *tt=new int[m+2];
	int j=1,c=-1;
    while(in>>x)
	{
		if(x!=-1)
		{
			if(c==-1)
				c=x;
			else
			{
				A=UF.Find(c);
				B=UF.Find(x);
				if(A!=B)
				{
					UF.Union(A,B);
					c=x;
				}
			}
		}
		else
		{
			if(c!=-1)
			{
				A=UF.Find(c);
				si[A]=j;
				is[j]=A;				
				c=x;
				prev[j]=j-1;
				next[j]=j+1;
				j++;
			}
			else if(c==-1)
			{
				is[j]=0;
				prev[j]=j-1;
				next[j]=j+1;
				j++;
			}
		}
	}
	if(x!=-1)
	{
		int d=UF.Find(x);
		si[d]=m+1;
		is[m+1]=d;
		prev[m+1]=m;
	}
	for(i=1;i<=n;i++)
	{
		A=UF.Find(i);
		j=si[A];
		if(j<=m)
		{
			tt[j]=i;
			int a=is[j];
			int b=is[next[j]];
			if(b!=0)
			{
				UF.Union(a,b);      //合并j和j+1
				B=UF.Find(is[j]);    //合并后的集合名
				si[B]=next[j];        
				is[next[j]]=B;
		    	prev[next[j]]=prev[j];
		    	next[prev[j]]=next[j];
			}
			else if(b==0)
			{
				si[a]=next[j];   
		    	is[next[j]]=is[j];
				prev[next[j]]=prev[j];
		    	next[prev[j]]=next[j];
			}
		}
	}
	for(i=1;i<=m;i++)
		out<<tt[i]<<' ';
	finish=clock();
	cout<<finish-start<<endl;
}