题目描述
有一个由 \(n\) 个点 \(m\) 条边组成的有向无环图,每个点出度至多为2。您需要标记一些点(不超过 \(\frac{4}{7}n\) 个)。标记一个点 \(u\) 将会删除所有与 \(u\) 连接的边。
您需要找到一种标记点的方案,使得删边后的图中每一条路径至多有一条边。
题解
不想说什么了,放个其他人的题解
题解链接
#include<bits/stdc++.h>
using namespace std;
inline int rd(){
int f=1,j=0;
char w=getchar();
while(!isdigit(w)){
if(w=='-')f=-1;
w=getchar();
}
while(isdigit(w)){
j=j*10+w-'0';
w=getchar();
}
return f*j;
}
const int N=200010;
int head[N],to[N*2],fro[N*2],tail;
int n,m,own[N],bel[N];
int ans[N],cnt;
inline void adlin(int x,int y){
to[++tail]=y,fro[tail]=head[x],head[x]=tail;
return ;
}
void work(){
n=rd(),m=rd();
tail=0,cnt=0;
for(int i=1;i<=n;i++)head[i]=bel[i]=0;
for(int i=1;i<=m;i++){
int x=rd(),y=rd();
adlin(y,x);
}
for(int i=1;i<=n;i++){
for(int k=head[i];k;k=fro[k]){
int x=to[k];
if(bel[x]==1)bel[i]=2;
if(bel[x]!=2&&!bel[i])bel[i]=1;
}
}
for(int i=1;i<=n;i++)if(bel[i]==2)ans[++cnt]=i;
printf("%d\n",cnt);
sort(ans+1,ans+cnt+1);
for(int i=1;i<=cnt;i++)printf("%d ",ans[i]);
printf("\n");
return ;
}
signed main(){
int T=rd();
while(T--)work();
return 0;
}
/*
1
10 17
1 4
1 10
2 4
8 10
3 8
5 8
9 10
3 9
7 8
2 10
5 9
6 10
6 9
4 7
7 9
8 9
4 6
*/
标签:head,int,题解,rd,CF1368E,tail,getchar
From: https://www.cnblogs.com/T-water/p/17236609.html