「NOIP模拟赛」Graph
「题目描述」
给出 N 个点，M 条边的有向图，对于每个点 v，求 A(v) 表示从点 v 出发，能到达的编号最大的点。
「输入格式」
第 1 行，2 个整数 N,M。 接下来 M 行，每行 2 个整数 Ui,Vi，表示边 ⟨Ui,Vi⟩。点用 1,2,…,N 编号。
「输出格式」
N 个整数 A(1),A(2),…,A(N)。
「样例输入」
4 3
1 2
2 4
4 3
「样例输出」
4 4 3 4
「数据范围」
对于 60% 的数据，1 ≤ N,K ≤ 10^3
对于 100% 的数据，1 ≤ N,M ≤ 10^5。
题解
反建图 bfs
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 |
#include<iostream> #include<cstdio> #include<cstring> #include<cstdlib> #include<set> #include<ctime> #include<queue> #include<cmath> #include<vector> #include<algorithm> #include<map> #define inf 1000000000 #define ll long long using namespace std; 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*10+ch-'0';ch=getchar();} return x*f; } int n,m,cnt; int last[100005],mark[100005],q[100005]; struct data{int to,next;}e[200005]; void insert(int u,int v) { e[++cnt].to=v;e[cnt].next=last[u];last[u]=cnt; } void bfs(int x) { int head=0,tail=1; q[0]=x;mark[x]=x; while(head!=tail) { int now=q[head];head++; for(int i=last[now];i;i=e[i].next) if(!mark[e[i].to]) { mark[e[i].to]=x; q[tail++]=e[i].to; } } } int main() { n=read();m=read(); for(int i=1;i<=m;i++) { int u=read(),v=read(); insert(v,u); } for(int i=n;i;i--)if(!mark[i])bfs(i); for(int i=1;i<=n;i++)printf("%d ",mark[i]); return 0; } |
Subscribe
计数器 9851267
OI 课件=>
OI 课件=>