2 条题解
-
0
#include<bits/stdc++.h> using namespace std; const int N=1e5+10; vector<int>G[N]; queue<int>q; int ind[N],f[N],milk[N]; bool ism[N]; int n,m,sum; void topo() { sum=0;memset(ism,0,sizeof(ism));memset(milk,0,sizeof(milk)); for(int i=1;i<=n;i++) { if(!ind[i]) { q.push(i); ism[i] = true; //标记源点 milk[i] = 1; //记录每个源点的流量 sum++; //一共有多少个源点(总流量) } } while(!q.empty()) { int x= q.front();q.pop(); if(G[x].size()>1) continue; //某点的出度大于1,说明该点的后继节点不可能为关键点 for(int y:G[x]) { ind[y]--; milk[y]+=milk[x]; if(!ind[y]) q.push(y); } } } int main() { scanf("%d",&n); for(int i=1,x,y;i<n;i++) { scanf("%d%d",&x,&y); G[x].push_back(y); ind[y]++; } topo(); for(int i=1;i<=n;i++) { if(!ism[i]&&milk[i]==sum) //不是源点且来自所有源点的流量都流经该点 { printf("%d\n",i); } } return 0; } -
0
#include<bits/stdc++.h> using namespace std; const int N=1e5+10; vector<int>G[N]; queue<int>q; int ind[N],f[N],milk[N]; bool ism[N]; int n,m,sum; void topo() { sum=0;memset(ism,0,sizeof(ism));memset(milk,0,sizeof(milk)); for(int i=1;i<=n;i++) { if(!ind[i]) { q.push(i); ism[i] = True; //标记源点 milk[i] = 1; //记录每个源点的流量 sum++; //一共有多少个源点(总流量) } } while(!q.empty()) { int x= q.front();q.pop(); if(G[x].size()>1) continue; //某点的出度大于1,说明该点的后继节点不可能为关键点 for(int y:G[x]) { ind[y]--; milk[y]+=milk[x]; if(!ind[y]) q.push(y); } } } int main() { scanf("%d",&n); for(int i=1,x,y;i<n;i++) { scanf("%d%d",&x,&y); G[x].push_back(y); ind[y]++; } topo(); for(int i=1;i<=n;i++) { if(!ism[i]&&milk[i]==sum) //不是源点且来自所有源点的流量都流经该点 { printf("%d\n",i); } } return 0; }
- 1
信息
- ID
- 1580
- 时间
- 1000ms
- 内存
- 128MiB
- 难度
- 9
- 标签
- 递交数
- 10
- 已通过
- 4
- 上传者