8 solutions
-
4
题意
拓扑排序
思路
拓扑排序模板
不必多言重点在代码中的注释
代码
#include<iostream> #include<vector> #include<queue> #define N 114 using namespace std; int n; vector<int>g[N];//使用邻接表更方便 int deg[N]={0};//入度的存储 queue<int>q; void topo()//拓扑排序 { for(int i=1;i<=n;i++) { if(deg[i]==0)//先将入度为0的入队 { q.push(i); } } while(!q.empty()) { int u=q.front(); q.pop(); cout<<u<<" ";//输出节点 for(int i=0;i<(int)g[u].size();i++)//遍历子节点 { int v=g[u][i]; if((--deg[v])==0)//减减同时判0 { q.push(v);//为0入队 } } } } int main() { cin>>n;//输入 for(int i=1;i<=n;i++) { int x; cin>>x;//输入 while(x!=0) { g[i].push_back(x);//添加节点 deg[x]++; cin>>x;//输入 } } topo();//拓扑排序 return 0;//完结散花 }顶 顶顶顶顶 顶顶顶顶顶顶顶顶顶 顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶 顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶 顶顶顶顶 顶顶顶顶顶顶顶顶顶顶顶 顶顶顶顶顶顶顶 顶顶顶 顶顶顶顶顶 顶顶顶顶顶顶顶顶顶顶顶顶 顶顶顶顶 顶顶顶顶顶顶顶顶顶顶顶顶顶顶 顶顶顶顶 顶顶顶顶顶顶顶顶顶顶顶顶 顶顶顶顶顶顶顶顶顶顶顶 顶顶顶顶顶顶顶顶顶顶顶顶 顶顶顶顶顶顶顶顶顶顶顶顶顶顶 顶顶顶顶顶顶顶顶顶顶 顶顶顶顶顶顶 顶顶顶顶顶顶顶 顶顶顶顶 顶顶顶顶 顶顶顶顶顶 顶顶顶顶 顶顶顶顶 顶顶 顶顶顶顶顶 顶顶顶顶 顶顶顶顶 顶顶顶顶 顶顶顶顶顶 顶顶顶顶 顶顶顶顶 顶顶顶顶 顶顶顶顶顶 顶顶顶顶 顶顶顶顶 顶顶顶 顶顶顶顶顶 顶顶顶顶 顶顶顶顶 顶顶顶 顶顶顶顶顶 顶顶顶顶 顶顶顶顶 顶顶顶顶 顶顶顶顶顶 顶顶顶顶 顶顶顶顶 顶顶顶顶 顶顶顶顶顶 顶顶顶顶 顶顶顶顶 顶顶顶顶 顶顶顶顶顶 顶顶顶顶 顶顶顶顶 顶顶顶顶 顶顶顶顶顶 顶顶顶顶 顶顶顶 顶顶顶顶 顶顶顶顶顶 顶顶 顶顶顶顶顶 顶顶顶 顶顶顶 顶顶顶顶顶 顶顶顶顶顶顶顶顶顶顶 顶顶 顶顶 顶顶顶顶顶 顶顶顶顶顶顶顶顶顶 顶顶顶 顶顶顶顶 顶顶顶顶顶顶顶 顶顶顶 顶顶顶顶 顶顶顶顶顶顶 顶顶顶顶 顶顶顶顶 顶顶顶 顶顶顶顶顶 顶顶顶顶顶顶顶 顶顶顶顶顶顶 顶顶顶顶顶顶 顶顶顶顶顶顶 顶顶顶顶顶顶顶 顶顶顶顶顶 顶顶顶顶顶顶 顶顶顶顶顶 顶顶顶顶 顶顶顶 顶顶顶-
C23lvzekai
@ 2024-5-31 19:47:51
优质题解！！！❤️
-
-
2
C23huangminzhe LV 6 @ 2024-5-31 20:06:26
代码
#include <bits/stdc++.h> using namespace std; const int N = 105; vector<int> a[N]; int indg[N],n; bool f[N]; void tp(){ bool flag = 0; for (int i = 1;i <= n;i++){ if ((!f[i]) && !indg[i]){ printf("%d ",i); f[i] = 1; flag = 1; for (int j = 0;j < a[i].size();j++) indg[a[i][j]]--; } } if (flag) tp(); } int main(int argc, char **argv){ cin >> n; for (int i = 1;i <= n;i++){ int x; cin >> x; while (x != 0){ a[i].push_back(x); indg[x]++; cin >> x; } } tp(); return 0; } -
2
C23xuzhiyu
LV 5
@ 2024-5-31 19:43:40
#include <bits/stdc++.h> #define N 105 using namespace std; vector gg[N]; int in_degree[N] ; int n;
void init(){ cin>>n; for(int i=1;i<=n;i++){ int w; cin>>w; while(w!=0){ gg[i].push_back(w); in_degree[w]++; cin >> w; }
} } void topsort(){ queueque; for(int j=1;j<=n;j++) if(in_degree[j]==0){ que.push(j); } while(que.empty()==false){ int u=que.front(); que.pop(); cout<< u << " "; int sz=gg[u].size(); for (int i=0;i<sz;i++){ in_degree[gg[u][i]]--; if (in_degree[gg[u][i]]==0)que.push(gg[u][i]); } }
} int main(){ init(); topsort(); return 0;
}
-
1
C23pengweixuan
LV 9
@ 2024-6-22 15:33:31
#include<bits/stdc++.h> using namespace std; int n; queue<int> q; vector<int> fa[105]; int in[105]; int main(){ cin>>n; for(int i=1,v;i<=n;i++) while(cin>>v&&v) fa[i].push_back(v),in[v]++; for(int i=1;i<=n;i++) if(in[i]==0) q.push(i),cout<<i<<' '; while(!q.empty()){ int fr=q.front(); q.pop(); for(int v=0;v<fa[fr].size();v++) if(--in[fa[fr][v]]==0){ q.push(fa[fr][v]); cout<<fa[fr][v]<<' '; } } return 0; }bfs做法，优点是简洁
-
1
C23linzerui
LV 2
@ 2024-6-22 15:19:37
能用两行解决的事绝对不用三行 （纯整活，无恶意，能AC）
#include<bits/stdc++.h> using namespace std;const int e=1640/(20-10);vector<int>g[e];int rd[e],n;queue<int>q;void tp(){for(int i=1;i<=n;i++){if(!rd[i]){q.push(i);cout<<i<<' ';}}while(!q.empty()){int f=q.front();q.pop();for(int i=0;i<g[f].size();i++){if(!--rd[g[f][i]]){q.push(g[f][i]);cout<<g[f][i]<<' ';}}}}int main(){scanf("%d",&n);for(int i=1;i<=n;i++){int v;while(cin>>v){if(v){g[i].push_back(v);rd[v]++;}else break;} }tp();return 0;} -
1
C23yanzizheng
LV 6
@ 2024-5-31 20:05:03
#include<iostream> #include<vector> #include<queue> using namespace std; int n; int rd[101]; vector <int> d[101]; queue <int> q; int main() { cin >> n; for (int i=1;i<=n;i++){ int t; cin >> t; while(t!=0){ //对于每一行的输入，先输入一个数据，然后判断其是否为0 rd[t]++; //如果不是0则建边，子节点入度+1，否则跳出 d[i].push_back(t); cin >> t; } } for (int i=1;i<=n;i++){ //找出所有没有父亲节点的点并入队 if(rd[i]==0)q.push(i); } while(!q.empty()){ int u=q.front(); q.pop(); cout << u << " "; int sz=d[u].size(); for (int i=0;i<sz;i++){ //遍历当前节点的子节点 rd[d[u][i]]--; //子节点入度-1 if (rd[d[u][i]]==0)q.push(d[u][i]); //如果该子节点没有其他父亲（先辈），则输出 } } } -
0
C23xuzhiyu
LV 5
@ 2024-5-31 19:45:56
#include <bits/stdc++.h> #define N 105 using namespace std; vector gg[N]; int in_degree[N] ; int n;
void init(){ cin>>n; for(int i=1;i<=n;i++){ int w; cin>>w; while(w!=0){ gg[i].push_back(w); in_degree[w]++; cin >> w; }
} } void topsort(){ queueque; for(int j=1;j<=n;j++) if(in_degree[j]==0){ que.push(j); } while(que.empty()==false){ int u=que.front(); que.pop(); cout<< u << " "; int sz=gg[u].size(); for (int i=0;i<sz;i++){ in_degree[gg[u][i]]--; if (in_degree[gg[u][i]]==0)que.push(gg[u][i]); } }
} int main(){ init(); topsort(); return 0;
}
-
0
C23zhuanghaojun
LV 6
@ 2024-5-31 19:13:41
#include<bits/stdc++.h> using namespace std; vector<int>g[1000005]; int d[100001]; queue<int>q; int main(){ int n; cin>>n; for(int i=1;i<=n;i++){ int x; while(cin>>x){ if(x==0){ break; } else{ d[x]++; g[i].push_back(x); } } } for(int i=1;i<=n;i++){ if(d[i]==0){ q.push(i); } } while(!q.empty()){ int a=q.front(); q.pop(); cout<<a<<" "; int sz=g[a].size(); for(int i=0;i<sz;i++){ d[g[a][i]]--; if(d[g[a][i]]==0){ q.push(g[a][i]); } } } }-
C23panweiming
@ 2024-5-31 19:33:47
题意
拓扑排序
思路
拓扑排序模板
代码
#include<iostream> #include<vector> #include<queue> #define N 114 using namespace std; int n; vector<int>g[N];//使用邻接表更方便 int deg[N]={0};//入度的存储 queue<int>q; void topo()//拓扑排序 { for(int i=1;i<=n;i++) { if(deg[i]==0)//先将入度为0的入队 { q.push(i); } } while(!q.empty()) { int u=q.front(); q.pop(); cout<<u<<" ";//输出节点 for(int i=0;i<(int)g[u].size();i++)//遍历子节点 { int v=g[u][i]; if((--deg[v])==0)//减减同时判0 { q.push(v);//为0入队 } } } } int main() { cin>>n;//输入 for(int i=1;i<=n;i++) { int x; cin>>x;//输入 while(x!=0) { g[i].push_back(x);//添加节点 deg[x]++; cin>>x;//输入 } } topo();//拓扑排序 return 0;//完结散花 }
-
- 1