NC24193. [USACO 2018 Dec P]The Cow Gathering
描述
她们玩得很开心，但是现在到了她们应当离开的时间了，她们会一个接一个地离开。她们想要以某种顺序离开，使得只要至少还有两头奶牛尚未离开，所有尚未离开的奶牛都还有没有离开的朋友。此外，由于行李寄存的因素，有M对奶牛(ai,bi)必须满足奶牛ai要比奶牛bi先离开。注意奶牛ai和奶牛bi可能是朋友，也可能不是朋友。
帮助奶牛们求出，对于每一头奶牛，她是否可以成为最后一头离开的奶牛。可能会发生不存在满足上述要求的奶牛离开顺序的情况。
输入描述
输入的第1行包含两个空格分隔的整数N和M。
输入的第2≤i≤N行，每行包含两个整数xi和yi，满足1≤xi,yi≤N，xi≠yi，表示奶牛xi和奶牛yi是朋友关系。
输入的第N+1≤i≤N+M行，每行包含两个整数ai和bi，满足1≤ai,bi≤N，ai≠bi，表示奶牛ai必须比奶牛bi先离开聚会。
输入保证1≤N,M≤10^5。对于占总分20%的测试数据，保证N,M≤3000。
输出描述
输出N行，每行包含一个整数di，如果奶牛i可以成为最后一头离开的奶牛，则di=1，否则di=0。
示例1
输入:
5 1 1 2 2 3 3 4 4 5 2 4
输出:
0 0 1 1 1
C++14(g++5.4) 解法, 执行用时: 367ms, 内存消耗: 13924K, 提交时间: 2019-07-08 20:58:26
#include<bits/stdc++.h>
using namespace std;
#define maxn 100010
vector<int>vec[maxn],lim[maxn];
queue<int>que;
int top[maxn],ans[maxn],vis[maxn];
int bfs()
{
while(!que.empty())
{
int u=que.front(); que.pop();
if(top[u]==0) return u;
for(auto v:vec[u]){
top[v]--;
if(top[v]==1) que.push(v);
}
for(auto v:lim[u]){
top[v]--;
if(top[v]==1) que.push(v);
}
}
return -1;
}
void dfs(int u,int pre)
{
ans[u]=1;
for(auto v:vec[u]){
if(v==pre || vis[v]) continue;
dfs(v,u);
}
}
int main()
{
int n,m; cin>>n>>m;
for(int i=1;i<n;i++)
{
int u,v; cin>>u>>v;
vec[u].push_back(v);
vec[v].push_back(u);
top[u]++; top[v]++;
}
for(int i=1;i<=m;i++)
{
int u,v; cin>>u>>v;
lim[u].push_back(v);
top[v]++; vis[u]=1;
}
for(int i=1;i<=n;i++)
{
if(top[i]==1) que.push(i);
}
int rt=bfs();
if(rt==-1)
{
while(n--) cout<<"0"<<endl;
return 0;
}
dfs(rt,-1);
for(int i=1;i<=n;i++) cout<<ans[i]<<endl;
return 0;
}
C++11(clang++ 3.9) 解法, 执行用时: 220ms, 内存消耗: 10220K, 提交时间: 2019-06-10 22:31:14
#include<bits/stdc++.h>
using namespace std;
const int M=1e5+10;
int in[M],n,ans[M],vis[M],m;
vector<int>v[M];
void dfs(int u,int fa){
ans[u]=1;
for(int i=0;i<v[u].size();i++){
int y=v[u][i];
if(y==fa||vis[y])
continue;
dfs(y,u);
}
}
int main(){
queue<int>q;
scanf("%d%d",&n,&m);
for(int i=0;i<n-1;i++){
int x,y;
scanf("%d%d",&x,&y);
v[x].push_back(y);
v[y].push_back(x);
in[x]++;
in[y]++;
}
while(m--){
int x,y;
scanf("%d%d",&x,&y);
v[x].push_back(y);
vis[x]=1;
in[y]++;
}
for(int i=1;i<=n;i++){
if(in[i]==1)
q.push(i);
}
int root,cnt=0;
while(q.size()){
int c=q.front();
q.pop();
cnt++;
root=c;
for(int i=0;i<v[c].size();i++){
int y=v[c][i];
in[y]--;
if(in[y]==1)
q.push(y);
}
}
if(cnt<n){
for(int i=1;i<=n;i++)
puts("0");
}
else{
dfs(root,-1);
for(int i=1;i<=n;i++)
printf("%d\n",ans[i]);
}
return 0;
}