`
plussai
  • 浏览: 87820 次
  • 性别: Icon_minigender_1
  • 来自: 杭州
社区版块
存档分类
最新评论

LAC的tarjan(离线)算法---zoj_1141

 
阅读更多

          LCA就不解释了,这里主要再次复习一下LCA的tarjan的离线算法,所谓离线算法,就是把Q个查询先预存储起来,然后等预处理完成后,一次性处理Q个查询。相反所谓在线算法,即使输入一个查询就处理一个查询。今后会补上LCA的ST在线算法。

      tarjan我非常崇拜,他解决了图论中很多问题,基本上都是基于DFS的,比如SCC,LCA等,那么tarjan离线如何运行呢,其中要配合并查集来实现。算法从根结点开始DFS,党遍历到某个节点时,为该节点创建一个集合,集合的先祖为该节点,当该节点的子节点被标记为黑时(即该节点的所有子节点都完成处理),子节点所对应的集合和该节点对应的集合合并,集合的先祖为该节点。次过程伴随着DFS进行。

      DFS的过程其实也是查询的过程,当一个节点u被标记为黑,那么就在集合Q中找到查询(u,v)如果节点v也被标记为黑,那么LCA(u,v)就是节点v所在集合的先祖。

      下面分析一下复杂度,DPS为O(N),并查集总共为N次合并操作,N次make-set操作和Q次寻找先祖操作共为a(N)*(N+Q),a(N)为一常数,对于每一个标记为黑的节点,找到对于的查询为O(1),公为O(N),因此,整个tarjan操作为O(N+Q)。

      最后需要注意的是,tarjan在使用并查集union时,不能使用按秩合并。

zoj_1141

#include<iostream>
#include<cstdio>
#include<vector>
#include<string.h>
using namespace std;
int n,m;
int root[801];
int visit[801];
int res[801];
class node
{
public:
	int value;
	vector<node*>v;
};
class query
{
public:
	vector<int>target;
	int total;
	query()
	{
		this->total=0;
	}
};
class union_find_set      
{      
public:      
    const static int maximum=801;   
    int anc;      
    int father[maximum];      
    int count[maximum];    
    int rank[maximum];   
         
    union_find_set()      
    {      
        for(int i=0;i<maximum;i++)      
        {      
            this->father[i]=i;      
            this->count[i]=1;   
        this->rank[i]=0;      
        }      
    }      
    int getFather(int v)      
    {      
        if(father[v]==v)      
        {         
            return v;      
        }      
        else     
        {      
            return  father[v]=getFather(father[v]);      
        }             
    }      
    bool same(int x,int y)      
    {      
        return (getFather(x)==getFather(y));      
    }      
    bool judge(int x,int y)      
    {      
        int fx,fy;      
        fx=getFather(x);      
        fy=getFather(y);      
        if(fx==fy) return false;      
        else     
        {      
         /* if(rank[x]<rank[y])    
        {   
        	father[fx]=fy;      
                count[fy]+=count[fx];   
        }   
        else if(rank[x]>rank[y])   
        {   
        father[fy]=fx;   
            count[fx]+=count[fy];      
        }   
        else  
        {   
            father[fx]=fy;      
                count[fy]+=count[fx];   
        ++rank[fy];   
        }  */
		father[fx]=fy;
		 count[fy]+=count[fx]; 
            return true;          
        }      
              
    }      
    void init()      
    {      
        for(int i=0;i<maximum;i++)      
        {      
            this->father[i]=i;      
            this->count[i]=1;     
        	this->rank[i]=0;    
        }         
    }      
};   
vector<node*>l;
union_find_set ufset;
query qlist[801];
void dfs(node*p)
{
	int size=p->v.size();
	for(int i=0;i<size;i++)
	{
		dfs(p->v[i]);
		ufset.judge(p->v[i]->value,p->value);	
	}
	visit[p->value]=1;
	int size2=qlist[p->value].total;
	for(int i=0;i<size2;i++)
	{
		if(visit[qlist[p->value].target[i]]==1)
		{
			int a=qlist[p->value].target[i];
			++res[ufset.getFather(a)];
		}

	}
	return;
}
int main()
{
	freopen("e:\\zoj\\zoj_1141.txt","r",stdin);
	while(cin>>n)
	{
		memset(root,0,sizeof(root));
		memset(visit,0,sizeof(visit));
		memset(res,0,sizeof(res));
		l.clear();
		ufset.init();
		for(int i=1;i<=n;i++)
		{	
			node*p=new node;
			p->value=i;
			l.push_back(p);
		}
		for(int j=1;j<=n;j++)
		{
			int v,t;
			scanf("%d:(%d)",&v,&t);
			for(int i=1;i<=t;i++)
			{
				int index;
				cin>>index;
				//scanf("%d",&index);
				root[index]=1;
				l[v-1]->v.push_back(l[index-1]);
			}	
		}
		int q;
		cin>>q;
		//char c=getchar();
		memset(qlist,0,sizeof(qlist));
		int a,b;
		char c1,c2,c3;
		for(int i=1;i<=q;i++)
		{
			//scanf("(%d,%d)",&a,&b);
			cin>>c1>>a>>c2>>b>>c3;
			if(a!=b)
			{
			query qu;
			qlist[a].target.push_back(b);
			qlist[a].total++;
			qlist[b].target.push_back(a);
			qlist[b].total++;}
			else
			{
			query qu;
			qlist[a].target.push_back(b);
			qlist[a].total++;
			}
		}
		int r;
		for(int i=1;i<=n;i++)
		{
			if(root[i]==0)
			{	
				r=i;
				break;
			}
		}
		dfs(l[r-1]);
		for(int i=1;i<=n;i++)
		{
			if(res[i]!=0)
				cout<<i<<":"<<res[i]<<endl;
		}
		//cout<<r<<endl;
	}	
}

 

分享到:
评论

相关推荐

Global site tag (gtag.js) - Google Analytics