Codeforces Round #786 (Div. 3)
题意描述:
在一个DAG图中,要使得每个点的入度和出度均减少,求使得一个集合s内任意两点u、v,要么从u–>v, 要么v–>u。求集合s的最大值。
思路:
可以发现若干元素同属一个集合s,那么必定成为一条链,原图一旦分叉,那么分叉节点就无法满足条件,可将题意转换为DAG上求最长链。
解法1.(拓扑序 + 递推)(在图上跑DP,都需要拓扑排序)
拓扑序实际上就是将一个图,转化成多条链,类似线性。
反向建图,是为了从原图中出度为0的点进行倒推。(也可以正向建图,从入度为0的点进行更新)
可以发现in[3] = 0, in[2] = 1, in[1] = 2
按照拓扑序 3 –> 2 – > 1
可由3号点更新2号点和1号点,这样就符合递推原则,从小集合–>大集合。
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <bitset>
#include <unordered_map>
#define IOS ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define eb push_back()
using namespace std;
typedef long long ll;
const int INF = 0x3f3f3f3f;
const int maxn = 3e5 + 10;
typedef pair <int, int> PII;
int h[maxn], ne[maxn], e[maxn], idx, f[maxn];int n, m, in[maxn], out[maxn], IN[maxn];
void add(int u, int v)
{
e[idx] = v;
ne[idx] = h[u];
h[u] = idx ++;
}
void topsort()
{
queue <int> alls;
for(int i = 1 ; i <= n ; i ++)
{
f[i] = 1;
if(IN[i] == 0)
alls.push(i);
}
while(!alls.empty())
{
int temp = alls.front();
alls.pop();
for(int i = h[temp] ; i != -1 ; i = ne[i])
{
int j = e[i];
if(in[j] >= 2 && out[temp] >= 2)
f[j] = max(f[j], f[temp] + 1);
IN[j] --;
if(IN[j] == 0)
{
alls.push(j);
}
}
}
}
int main()
{
scanf("%d %d", &n, &m);
memset(h, -1, sizeof(h));
for(int i = 1 ; i <= m ; i ++)
{
int u, v;// u-->v
scanf("%d %d",&u, &v);
add(v, u);// v -- > u
out[v] ++, in[u] ++, IN[u] ++;
}
topsort();
int res = 1;
for(int i = 1 ; i <= n ; i ++)
res = max(res, f[i]);
printf("%d\n",res);
return 0;
}
解法2 记忆化爆搜
可以发现,因为dfs特性,会从当前点一直把当前分支所有都搜完才会结束。所以无论我们从哪个点开始搜,最后遍历的
时候还是会遍历到我们DP的起点,也就保证了结果的正确性
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <bitset>
#include <unordered_map>
#define IOS ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define eb push_back()
using namespace std;
typedef long long ll;
const int INF = 0x3f3f3f3f;
const int maxn = 2e5 + 10;
typedef pair <int, int> PII;
int h[maxn], ne[maxn], e[maxn], idx, in[maxn], out[maxn], f[maxn];
int res;
void add(int u, int v)
{
e[idx] = v;
ne[idx] = h[u];
h[u] = idx ++;
}
void dfs(int sta)
{
if(f[sta]) return ;
f[sta] = 1;
if(out[sta] <= 1) return ;
for(int i = h[sta] ; i != -1 ; i = ne[i])
{
int son = e[i];
dfs(son);
if(in[son] >= 2)
{
f[sta] = max(f[sta], f[son] + 1);
}
}
}
int main()//
{
int n, m;
scanf("%d %d", &n, &m);
memset(h, -1, sizeof(h));
for(int i = 1 ; i <= m ; i ++)
{
int u, v;
scanf("%d %d", &u, &v); // u -- > v
out[u] ++, in[v] ++;
add(u, v);
}
res = 1;
for(int i = 1 ; i <= n ; i ++)
{
dfs(i);
}
for(int i = 1 ; i <= n ; i ++)
res = max(res, f[i]);
printf("%d\n",res);
return 0;
}