直径#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          using namespace std;const int N=4e4+10;int d[N],head[N],ver[N],next[N],edg[N];bool vis[N];int tot,ans,n,m,s,t;void init(){ tot=0; ans=0; memset(head,0,sizeof(head)); memset(next,0,sizeof(next)); }void add(int x,int y,int z){ ver[++tot]=y; next[tot]=head[x]; head[x]=tot; edg[tot]=z; }void bfs(int x){ memset(d,0,sizeof(d)); memset(vis,0,sizeof(vis)); queue
          
            q; q.push(x); vis[x]=1; ans=0; while(q.size()) { int cur=q.front(); q.pop(); for(int i=head[cur];i;i=next[i]) { int y=ver[i]; if(!vis[y]) { d[y]=d[cur]+edg[i]; if(d[y]>ans) { ans=d[y]; t=y; } q.push(y); vis[y]=1; } } }}int main(){ ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); while(cin>>n>>m) { init(); for(int i=1;i<=m;i++) { int u,v,w; char c; cin>>u>>v>>w>>c; add(u,v,w); add(v,u,w); } bfs(1); s=t; bfs(s); cout<
           
            <
           
          
         
        
       
      
     
    

dfs序深度重心#include
    
     using namespace std;typedef long long ll;const int N=1e5+10;int ver[N],next[N],edg[N],a[N],d[N],size[N],head[N];bool vis[N];int tot=0,pos,ans,cnt;int n,m;void init(){    tot=0;    ans=1e5+10;    memset(vis,0,sizeof(vis));    memset(size,0,sizeof(size));    memset(head,0,sizeof(head));    memset(next,0,sizeof(next));}void add(int x,int y,int z){    ver[++tot]=y; next[tot]=head[x];    edg[tot]=z; head[x]=tot;}void dfs(int x){    a[++cnt]=x;    size[x]=1;    vis[x]=1;    int ma=0;    for(int i=head[x];i;i=next[i])    {        int y=ver[i];        if(!vis[y])        {            d[y]=d[x]+1;            dfs(y);            size[x]+=size[y];            ma=max(ma,size[y]);        }    }    ma=max(ma,n-size[x]);    a[++cnt]=x;    if(maans)    {        ans=ma;        pos=x;    }}int main(){    while(cin>>n>>m)    {        init();        for(int i=1;i<=m;i++)        {            int u,v,w;            cin>>u>>v>>w;            add(u,v,w);            add(v,u,w);        }        dfs(1);        for(int i=1;i<=cnt;i++) cout<
     
      <<" \n"[i==cnt];        for(int i=1;i<=n;i++) cout<
      
       <<" \n"[i==n];        for(int i=1;i<=n;i++) cout<
       
        <<" \n"[i==n];        cout<
        
         <<" "<
         
          <
         
        
       
      
     
    

拓扑排序#include
    
     using namespace std;typedef long long ll;const int N=1e5+10;int head[N],ver[N],next[N],edg[N],d[N],a[N];bool vis[N];int tot,cnt,n,m;void add(int x,int y,int z){    ver[++tot]=y;    next[tot]=head[x];    head[x]=tot;    edg[tot]=z;    d[y]++;}void topsort(){    queue
     
       q;    for(int i=1;i<=n;i++) if(d[i]==0) q.push(i);    while(q.size())    {        int cur=q.front(); q.pop();        a[++cnt]=cur;        for(int i=head[cur];i;i=next[i])        {            int y=ver[i];            --d[y];            if(!d[y]) q.push(y);        }    }}int main(){    while(cin>>n>>m)    {        tot=0;        cnt=0;        memset(vis,0,sizeof(vis));        memset(head,0,sizeof(head));        memset(next,0,sizeof(next));        memset(d,0,sizeof(d));        for(int i=1;i<=m;i++)        {            int u,v,w;            cin>>u>>v>>w;            add(u,v,w);            //add(v,u,w);        }        topsort();        for(int i=1;i<=cnt;i++) cout<
      
       <<" \n"[i==cnt];    }    return 0;}