B3862 图的遍历（简单版） - 洛谷 | 计算机科学教育新生态
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N = 1e5+10;
int head[N];
int tot;
int n,m;
int pos;
bool vis[N];
struct Edge{int next;int to;
}e[N];
void init()
{for(int i = 1 ; i <= n ; i++)head[i] = -1;
}
void add(int u,int v)
{++tot;e[tot].next = head[u];e[tot].to = v;head[u] = tot;
}
void dfs(int current)
{if(current > pos)pos = current;int k = head[current];//取出连接第一条边的信息 while(k != -1){int to = e[k].to;//指向的点int temp = head[to];//链表to点连接第一条边 if(vis[to] == false){ vis[to] = true;dfs(to);}k = e[k].next;}
}
int main(void)
{cin >> n >> m;init();for(int i = 1 ; i <= m ; i++){int u,v;cin >> u >> v;add(u,v);}for(int i = 1 ; i <= n ; i++){memset(vis,false,sizeof(vis));vis[i] = true;pos = i;dfs(i);cout << pos << " "; }return 0;
}P3916 图的遍历 - 洛谷 | 计算机科学教育新生态
90分
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N = 1e5+10;
int head[N];
int tot;
int n,m;
int pos;
bool vis[N];
struct Edge{int next;int to;
}e[N];
void init()
{for(int i = 1 ; i <= n ; i++)head[i] = -1;
}
void add(int u,int v)
{++tot;e[tot].next = head[u];e[tot].to = v;head[u] = tot;
}
void dfs(int current)
{if(current > pos)pos = current;int k = head[current];//取出连接第一条边的信息 while(k != -1){int to = e[k].to;//指向的点int temp = head[to];//链表to点连接第一条边 if(vis[to] == false){ vis[to] = true;dfs(to);}k = e[k].next;}
}
int main(void)
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin >> n >> m;init();for(int i = 1 ; i <= m ; i++){int u,v;cin >> u >> v;add(u,v);}for(int i = 1 ; i <= n ; i++){memset(vis,false,sizeof(vis));vis[i] = true;pos = i;dfs(i);cout << pos << " "; }return 0;
}100分
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N = 1e5+10;
int head[N];
int tot;
int n,m;
int pos;
bool vis[N];
int ans[N];
struct Edge{int next;int to;
}e[N];
void init()
{for(int i = 1 ; i <= n ; i++)head[i] = -1;
}
void add(int u,int v)
{++tot;e[tot].next = head[u];e[tot].to = v;head[u] = tot;
}
void dfs(int current,int maxpos)
{if(vis[current] == false)ans[current] = maxpos;vis[current] = true;int k = head[current];while(k != -1){int to = e[k].to;//指向的点int temp = head[to];//链表to点连接第一条边 if(vis[to] == false){ ans[to] = maxpos;vis[to] = true;dfs(to,maxpos);}k = e[k].next;}
}
int main(void)
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin >> n >> m;init();for(int i = 1 ; i <= m ; i++){int u,v;cin >> u >> v;add(v,u);//方向建立边 }for(int i = n ; i >= 1 ; i--){dfs(i,i); }for(int i = 1 ; i <= n ; i++)cout << ans[i] << " ";return 0;
}P1700 [USACO19OPEN] Milk Factory B - 洛谷 | 计算机科学教育新生态
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N = 1e5+10;
int head[N];
int ans = 1e9;
int cnt;
int tot;
int n;
bool vis[N];
struct Edge{int next;int to;
}e[N];
bool found;
void add(int u,int v)
{tot++;e[tot].next = head[u];e[tot].to = v;head[u] = tot;
}
void dfs(int current)
{vis[current] = true;cnt++;int k = head[current];while(k != -1){int to = e[k].to;if(vis[to] == false){vis[to] = true;dfs(to);}k = e[k].next;}
}
int main(void)
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin >> n;for(int i = 1 ; i <= n ; i++)head[i] = -1;for(int i = 1 ; i <= n-1 ; i++){int u,v;cin >> u >> v;add(v,u);//反向建立边}for(int i = 1 ; i <= n ; i++){cnt = 0;memset(vis,false,sizeof(vis));dfs(i);if(cnt == n){found = true;ans = min(ans,i);}}if(found)cout << ans;elsecout << -1;return 0;
}