<题目链接>
题目大意：
n个人，m条关系，每条关系a >= b，说明a，b之间是可比较的，如果还有b >= c，则说明b，c之间，a，c之间都是可以比较的。问至少需要多少个集合使得每个集合内的人都是不可比较的。
解题分析：
将所给的关系当成有向边，根据题意，同一强连通分量中的任意两点不能分到一组，所以我们先将整张图进行缩点，缩点后"点"的中点的数量当做点权，然后就可以转化为最长路的求解了。这里比较难想，因为同一连通分量中的点不能在一组，所以必然要将它们全部排成一条。因为要求最少分成的组，所以我们只需要将整张图的最长关键路径(最大点权和的路径)找出即可，这样可以将不在关键路径上的"点"中的所有的点与最长路径上的不同点分配到一组，因为它们不属于一个连通分量，所以这样分配，每组之间的所有点仍然是不可比较的。又因为这是最长路径，所以每次必然能够最长路径之外的"点"中所有的点与最短路径上的点一 一分配到一组。
#include <cstdio>
#include <cstring>
#include <queue>
#include <algorithm>
using namespace std;
#define INF 0x3f3f3f3f
const int N = 1e5+;
const int M = 3e5+;
struct Edge{
int v, nxt;
} edge[M], edg[M];
int n,m,tott, tot, ord, scc, top;
int cnt[N], dp[N], head[N], hea[N], vis[N], deg[N], dfn[N], low[N], belong[N],stk[N]; void init(){
tot = scc = tott = ord = top = ;
memset(head, -, sizeof(head));
memset(hea, -, sizeof(hea));
memset(dfn, , sizeof(dfn));
memset(dp, , sizeof(dp));
memset(cnt,,sizeof(cnt));
}
void Add(int u, int v) {
edge[tot].v = v; edge[tot].nxt = head[u];
head[u] = tot++;
}
void add(int u, int v) {
edg[tott].v = v; edg[tott].nxt = hea[u];
hea[u] = tott++;
}
void tarjan(int u) {
dfn[u] = low[u] = ++ord;
stk[++top]=u; vis[u] = ;
for(int i = head[u]; ~i; i = edge[i].nxt) {
int v = edge[i].v;
if(!dfn[v]){
tarjan(v);
low[u]=min(low[u],low[v]);
}else if(vis[v])low[u]=min(low[u],dfn[v]);
}
if(low[u] == dfn[u]) {
++scc;
while(true){
int v=stk[top--];
belong[v] = scc;
cnt[scc]++;
vis[v] = ;
if(v==u)break;
}
}
}
//将"点"中点的数量作为这个点的点权，然后求出最大点权的路径
//dp[u]表示，以u为起点的最长路径
int DFS(int u) {
if(dp[u]) return dp[u];
int ans = cnt[u];
for(int i = hea[u]; ~i; i = edg[i].nxt) {
int v = edg[i].v;
ans = max(ans, DFS(v) + cnt[u]);
}
return dp[u] = ans;
}
int main() {
while(~scanf("%d%d", &n, &m)) {
init();
for(int i = ; i < m; i++) {
int u,v;scanf("%d%d", &u, &v);
Add(u, v);
}
for(int i = ; i <= n; i++)
if(!dfn[i]) tarjan(i);
for(int u = ; u <= n; u++)
for(int i = head[u]; ~i; i = edge[i].nxt) {
int v = edge[i].v;
if(belong[u] != belong[v]) {
add(belong[u], belong[v]);
}
}
int ans = -;
for(int i = ; i <= scc; i++)
ans = max(ans, DFS(i)); //所有点为起点的最长路径即为整张图的最长路径
printf("%d\n", ans);
}
}
2018-11-26