day8
2025-02-05 14:25:22
发布于：上海
34阅读
0回复
0点赞
家谱树
#include<bits/stdc++.h>
using namespace std;
vector<int> tr[110];
int in[110];
int n,m;
int main(){
cin>>n>>m;
for(int i=1;i<=m;i++){
int a,b;
cin>>a>>b;
tr[a].push_back(b);
in[b]++;
}
queue<int>q;
for(int i=1;i<=n;i++){
if(in[i]==0){
q.push(i);
}
}
while(q.size()){
int u = q.front();
q.pop();
cout<<u<<" ";
for(int son:tr[u]){
if(--in[son]==0)q.push(son);
}
}
}
拓扑排序
#include<bits/stdc++.h>
using namespace std;
int n,m;
vector<int> tr[200010];
int in[200010];
int main(){
cin>>n>>m;
for(int i=1;i<=m;i++){
int a,b;
cin>>a>>b;
tr[a].push_back(b);
in[b]++;
}
queue<int> q;
for(int i=1;i<=n;i++)if(in[i]==0)q.push(i);
vector<int> ans;
while(q.size()){
int u = q.front();
q.pop();
n--;
ans.push_back(u);
for(int son:tr[u]){
if(--in[son]==0){
q.push(son);
}
}
}
if(n==0){
cout<<"YES"<<endl;
for(int x:ans)cout<<x<<" ";
}else cout<<"NO";
return 0;
}
安全节点
#include<bits/stdc++.h>
using namespace std;
vector<int> g[100010];
int n,m,in[100010];
int main(){
cin>>n>>m;
for(int i = 1;i<=m;i++){
int u,v;
cin>>u>>v;
g[v].push_back(u);
in[u]++;
}
queue<int> q;
vector<int> ans;
for(int i = 1;i<=n;i++){
if(in[i]==0)q.push(i);
}
while(q.size()){
int u = q.front();
q.pop();
ans.push_back(u);
for(int son:g[u])if(--in[son]==0)q.push(son);
}
sort(ans.begin(),ans.end());
cout<<ans.size()<<endl;
for(int i = 0;i<ans.size();i++)cout<<ans[i]<<" ";
}
无垠的树
#include<bits/stdc++.h>
using namespace std;
int t,n,k;
vector<int> tr[400010];
int dg[400010];
int ans[400010];
int main(){
cin>>t;
while(t--){
cin>>n>>k;
for(int i=1;i<=n;i++){
tr[i].clear();//清空邻接表
dg[i] = 0;
}
for(int i=1;i<=n-1;i++){//无向图
int x,y;
cin>>x>>y;
tr[x].push_back(y);
tr[y].push_back(x);
dg[x]++;
dg[y]++;
}
//topsort
queue<int> q;
for(int i=1;i<=n;i++){
if(dg[i]==1){
q.push(i);
ans[i] = 1;
}
}
while(q.size()){
int u = q.front();
q.pop();
for(int son:tr[u]){
if(--dg[son]==1){
ans[son] = ans[u] + 1;
q.push(son);
}
}
}
int res = 0;
for(int i=1;i<=n;i++)if(ans[i]>k)res++;//如果当前点在 k次操作以后被删掉 答案++
cout<<res<<endl;
}
return 0;
}
QQ 聊天群
#include <bits/stdc++.h>
using namespace std;
int T, n, k;
vector<int> edge[200010];
int d[200010], t[200010];
int main(){
cin >> T;
while (T--){
cin >> n>> k;
for (int i=1;i<=n;i++){
edge[i].clear();
d[i] = t[i] = 0;
}
for (int i=1;i<=k;i++){
for (int j=1;j<=n;j++){
cin >> t[j];
if (j >= 3) {
edge[t[j-1]].push_back(t[j]);
d[t[j]] ++;
}
}
}
queue<int> q;
for (int i=1;i<=n;i++){
if (d[i] == 0){
q.push(i);
}
}
while (q.size()){
int u = q.front();
q.pop();
n--;
for (int j: edge[u]){
d[j] --;
if (d[j] == 0){
q.push(j);
}
}
}
if (n==0) cout << "YES\n";
else cout << "NO\n";
}
return 0;
}
食物链
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 5005;
const int mod = 80112002;
std::vector<int> g[N];
int in[N];// 每个点的入度
int out[N];// 每个点的出度
ll f[N];// f[i]:到第 i 个点的方案数
void solve() {
int n, m;
cin >> n >> m;
for (int i = 1; i <= m; i++) {
int u, v;
cin >> u >> v;
g[u].push_back(v);
in[v]++;
out[u]++;
}
queue<int>q;
for (int i = 1; i <= n; i++) {
if (in[i] == 0) {
q.push(i);
f[i] = 1;
}
}
while (!q.empty()) {
int u = q.front();
q.pop();
for (int v : g[u]) {
(f[v] += f[u]) %= mod;
if (--in[v] == 0) {
q.push(v);
}
}
}
ll ans = 0;
for (int i = 1; i <= n; i++) {
if (out[i] == 0)(ans += f[i]) %= mod;
}
cout << ans << '\n';
}
int main()
{
solve();
}
这里空空如也
有帮助，赞一个