dfs90求教
  • 板块P3916 图的遍历
  • 楼主__a__a
  • 当前回复1
  • 已保存回复1
  • 发布时间2025/1/23 19:36
  • 上次更新2025/1/23 22:12:00
查看原帖
dfs90求教
1445353
__a__a楼主2025/1/23 19:36
#include<iostream>
#include<cstring>
using namespace std;
const int N = 100010,M = 100010;
int h[N],e[2*M],nex[2*M],idx = 1;
bool istrue[N];
void add(int a,int b){
    e[idx] = b;
    nex[idx] = h[a];
    h[a] = idx++;
}
void dfs(int u,int& MAX){
    istrue[u] = true;
    MAX = max(MAX,u);
    for(int i = h[u]; i != -1 ; i = nex[i]){
        int j = e[i];
        if(!istrue [j]){
            dfs(j,MAX);
        }
    }
}
int main(){
    int n,m;
    cin>>n>>m;
    memset(h,-1,sizeof(h));
    for(int i=1;i<=m;i++){
        int a,b;
        cin>>a>>b;
        add(a,b);
    }
    for(int i=1;i<=n;i++){
         memset(istrue,false,sizeof(istrue));
        int MAX = 1;
        dfs(i,MAX);
        cout<<MAX<<' ';
    }
    return 0;
}
2025/1/23 19:36
加载中...