【强连通分量缩点】【DFS】【动态规划】Urozero Autumn Training Camp 2016 Day 5: NWERC-2016 Problem B. British Menu

有向图，不经过重复点的最长链，强连通分量大小不超过5。

每个强连通分量内部暴力预处理任意两对点之间的最长路，外面DAG上dp。

不是很好写，但是预处理完了之后，可以重构每个强连通分量内部的结构，然后整个就变成一张DAG了，就很方便了。

#include <cmath>

#include <cstdio>

#include <cstring>

#include <iostream>

#include <algorithm>

#include <vector>

#define MAX_V 200005

using namespace std;

int n,ans,ans1[MAX_V],ans2[MAX_V],c[MAX_V][6],cnum[MAX_V],id[MAX_V],dis[MAX_V][6],m;

vector<int> G[MAX_V];

vector<int> rG[MAX_V];

vector<int> vs;

bool used[MAX_V];

int cmp[MAX_V];

void add_edge(int from,int to)

{

	G[from].push_back(to);

	rG[to].push_back(from);

}

void dfs(int v)

{

	used[v]=1;

	for(int i=0;i<G[v].size();++i)

	{

		if(!used[G[v][i]])

			dfs(G[v][i]);

	}

	vs.push_back(v);

}

void rdfs(int v,int k)

{

	used[v]=1;

	cmp[v]=k;

	for(int i=0;i<rG[v].size();++i)

	{

		if(!used[rG[v][i]])

		rdfs(rG[v][i],k);

	}

}

int scc()

{

	memset(used,0,sizeof used);

	vs.clear();

	for(int v=1;v<=n;v++)

	{

		if(!used[v]) dfs(v);

	}

	memset(used,0,sizeof used);

	int k=1;

	for(int i=vs.size()-1;i>=0;--i)

	{

		if(!used[vs[i]])

		rdfs(vs[i],k++);

	}

	return k;

}

void cal(int now,int nowid,int f,int nowdis)

{

	used[now]=1;

	dis[now][nowid]=max(dis[now][nowid],nowdis);

	for(int i=0;i<G[now].size();++i)

	if(cmp[G[now][i]]==f&&!used[G[now][i]])

	{

		cal(G[now][i],nowid,f,nowdis+1);

	}

	used[now]=0;

	return;

}

int get2(int now);

int get1(int now)

{

	if(ans1[now]!=-1) return ans1[now];

	int nowans=1;

	for(int i=0;i<rG[now].size();i++)

	if(cmp[rG[now][i]]!=cmp[now])

	{

		nowans=max(nowans,get2(rG[now][i])+1);

	}

	return ans1[now]=nowans;

}

int get2(int now)

{

	if(ans2[now]!=-1) return ans2[now];

	int nowans=-1;

	for(int i=1;i<=cnum[cmp[now]];++i)

	{

		nowans=max(nowans,get1(c[cmp[now]][i])+dis[now][i]);

	}

	return ans2[now]=nowans;

}

int main()

{

	scanf("%d%d",&n,&m);

	int u,v;

	for(int i=1;i<=m;++i)

	{

		scanf("%d%d",&u,&v);

		add_edge(u,v);

	}

	scc();

	memset(used,0,sizeof used);

	for(int i=1;i<=n;++i)

	{

		ans1[i]=ans2[i]=-1;

		c[cmp[i]][++cnum[cmp[i]]]=i;

		id[i]=cnum[cmp[i]];

		cal(i,id[i],cmp[i],0);

	}

	for(int i=1;i<=n;++i)

	{

		ans=max(ans,get2(i));

	}

	cout<<ans;

	return 0;

}