首页 > 代码库 > UVa11324 最大团

UVa11324 最大团

题意:一个有向图中,求一个节点数最多的结点集,使得该结点任意两点u和v, 要么u可达v,要么v可达u,u和v互相可达也可以。

思路:这一看就知道是最大团的定义了,可以说是最大团的模板题,可以先强连通缩点,缩点后就成了DAG(有向无环图),强连通里的点都可以满足要求,再求DAG的最长路径极为结果,每个强连通缩点后的点权即为该强连通的结点个数,而DAG求路径可用动态规划求。

一开始我记录每个连通图结点个数时,在tarjan算法里面写,可是WA,后来放在缩点的地方就对了。这个真心不知道为什么了。

#include<stdio.h>#include<string.h>const int maxn = 3000;const int maxm = 50009;struct node{	int v,next;}eg[maxm],tree[maxm];int head[maxn],root[maxn];int dfn[maxn],low[maxn],sta[maxn],insta[maxn],sum[maxn],belong[maxn];int tot,color,Index,top,n;int dp[maxn];inline int max(int a,int b){return a > b ? a : b;}inline int min(int a,int b){return a < b ? a : b;}void add(int a,int b){	eg[tot].v = b;	eg[tot].next = head[a];	head[a] = tot++;}void addt(int a,int b){	tree[tot].v = b;	tree[tot].next = root[a];	root[a] = tot++;}//求强连通void tarjan(int u){	dfn[u] = low[u] = ++Index;	sta[top++] = u;	insta[u] = 1;	for(int i =head[u];i+1;i=eg[i].next)	{		int v = eg[i].v;		if(!dfn[v])		{			tarjan(v);			low[u] = min(low[u],low[v]);		}if(insta[v])		{			low[u] = min(low[u],dfn[v]);		}	}	if(low[u] == dfn[u])	{		color++;		int v;		do		{			v= sta[--top];			insta[v] = 0;			belong[v] = color;		//	sum[color] ++;  //为什么不可以在这里加		}while(u != v);	}} //缩点void Buildtree(){	tot = 0;	for(int u = 1;u <= n;u++)	{		sum[belong[u]] ++;	//每个连通图的结点个数		for(int i=head[u];i+1;i=eg[i].next)		{			int v= eg[i].v;			if(belong[u] != belong[v])			{				addt(belong[u],belong[v]);			}		}	}}void init(){	memset(dp,0,sizeof(dp));	memset(dfn,0,sizeof(dfn));	memset(low,0,sizeof(low));	memset(head,-1,sizeof(head));	memset(root,-1,sizeof(root));	memset(insta,0,sizeof(insta));	memset(belong,0,sizeof(belong));	memset(sum,0,sizeof(sum));	tot = Index = top = color = 0;}int Clique(int u)  	//dp求DAG的最长路径{      if(dp[u]>0) return dp[u];  	dp[u]=sum[u];      for(int i=root[u];i+1;i=tree[i].next)      {          int v=tree[i].v;          dp[u]=max(dp[u],Clique(v)+sum[u]);      }      return dp[u];  }    void work(){	int u,i,ans =0;	tot = 0;	for( u =1;u<=n;u++)	{		if(!dfn[u]) tarjan(u);	}	Buildtree();	for(i=1;i<=color;i++)	{		ans = max(ans,Clique(i));	}	printf("%d\n",ans);}int main(){	int m,i,a,b,t;	scanf("%d",&t);	while(t--)	{		init();		scanf("%d%d",&n,&m);		for(i=0;i<m;i++)		{			scanf("%d%d",&a,&b);			add(a,b);		}		work();	}	return 0;}/*25 51 22 33 14 15 25 51 22 33 14 15 2*/