题意 有一个序列 ，有1，0，2三种点，每个点之间是有向边，如果存在一条路径从1出发中间不要有1并且以2结尾，这些点都是有趣点，否则不是有趣的。 解题报告：我们将1的点bfs ，将2的点反向bfs，那么一个点是有趣点等价于他同时被1，2点所遍历过。 代码：
#include<iostream> #include<cstring> #include<vector> #include<algorithm> #include<queue> using namespace std; typedef long long ll; const int N=100010; vector<int>v[N][2]; bool vis[N][2]; int n,m; int d[N]; void bfs(int id,int k) { queue<int>q; for(int i=1;i<=n;i++) if(d[i]==id) { vis[i][k]=1; q.push(i); } while(q.size()) { int t=q.front(); q.pop(); for(int i=0;i<v[t][k].size();i++) { int j=v[t][k][i]; if(!vis[j][k] ) { if(d[j]!=1) q.push(j); vis[j][k]=true; } } } } int main() { cin >> n >> m; for(int i=1;i<=n;i++) cin >> d[i]; while(m--) { int a,b; cin>>a>>b; v[a][0].push_back(b); v[b][1].push_back(a); } bfs(1,0),bfs(2,1); for(int i=1;i<=n;i++) cout<<(vis[i][0]&&vis[i][1])<<' '; cout<<endl; return 0; }