给定一个DAG,尽可能少的选出一些不相邻的控制节点,使得整个图被控制,每个控制节点可以控制它本身和所有它指向的点
蒟蒻考场的时候一直在想一种情况,拓扑排序分层图,奇数层选择控制点,甚至考虑了奇数层是不是需要全选…实际上不需要分层,因为奇数层是肯定要全选的(偶数层都不选,没有点控制奇数层的点)
所以只需要按照拓扑序,从小到大枚举,如果没被控制,那么一定没人可以控制它了(此时它的入度为0),它就是一个新的控制点,此时把它的所有出边的点控制
这样选就是最小的答案了,考试的时候考虑复杂了,这是通过率第二的题目,下次一定要先想简单的贪心想法,其实也和没有注意到点不光要控制别人,一定要控制自己,如果没人控制自己,自己是必须要选自己这个性质有关
#include<cstdio>
#include<iostream>
#include<cstring>
#include<string>
#include<algorithm>
#include<cmath>
#include<vector>
#include<queue>
#include<map>
#include<stack>
#include<set>
#define NDEBUG
#include <assert.h>
using namespace std;
typedef vector<int> vi;
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef unsigned int ui;
inline int read() {
int x = 0, f = 1;
char ch = getchar();
while(ch < '0' || ch > '9') {
if(ch == '-') f = -1;
ch = getchar();
}
while(ch >= '0' && ch <= '9') {
x = (x << 1) + (x << 3) + (ch ^ 48);
ch = getchar();
}
return x * f;
}
#define endl '\n'
#define rd read()
#define pb push_back
#define mst(a, b) memset((a), (b), sizeof(a));
#define inf 0x3f3f3f3f
#define linf 0x3f3f3f3f3f3f3f3f
#define ls (u << 1)
#define rs (u << 1 | 1)
#define mod ((int)1e9+7)
#define maxn (int)(1e5+5)
int n, m, ans, in[maxn];
vector <int> e[maxn];
bool vis[maxn], ctr[maxn];
queue <int> q;
void inp() {
cin >> n >> m;
for(int i = 1; i <= m; ++i) {
int u = rd, v = rd;
++in[v];
e[u].pb(v);
}
}
void topo() {
for(int i = 1; i <= n; ++i) {
if(!in[i]) {
q.push(i);
ctr[i] = true;
vis[i] = true;
++ans;
}
}
while(!q.empty()) {
int u = q.front();
q.pop();
for(unsigned int i = 0; i < e[u].size(); ++i) {
int v = e[u][i];
--in[v];
if(ctr[u]) vis[v] = true;
if(!in[v]) {
if(!vis[v]) {
ctr[v] = vis[v] = true, ++ans;
// printf("u = %d, v = %d\n", u, v);
}
q.push(v);
}
}
}
printf("%d\n", ans);
}
int main() {
#ifndef ONLINE_JUDGE
freopen("D:\\Chrome Downloadings\\input.txt", "r", stdin);
freopen("D:\\Chrome Downloadings\\output.txt", "w", stdout);
#endif
inp();
topo();
return 0;
}