训练题目网址（密码hpuacm2017）： https://vjudge.net/contest/244053

 

记好下面的模板

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1000+10;

int ma[MAXN][MAXN];
int vis[MAXN];
int n, m;
void topo_sort()
{
    for( int i=1; i<=n; i++ )   // 因为有n个顶点一定要循环n次
    {
        for( int j=1; j<=n; j++ )   // 每次从头开始找入度为0的顶点
        {
            if( vis[j] == 0 )
            {
                vis[j]--;   // 删除的点标记为-1
                printf("%d", j);
                if( i != n )
                    printf(" ");
                else
                    printf("\n");
                for( int k=1; k<=n; k++ )   // 然后找与该顶点相连的顶点以及边
                {
                    if( ma[j][k] == 1 )
                        vis[k] --;
                }
                break;
            }
        }
    }
}

int main()
{
    while( cin >> n >> m )
    {
        int x, y;
        memset(ma, 0, sizeof(ma));
        memset(vis, 0, sizeof(vis));
        for( int i=1; i<=m; i++ )
        {
            scanf("%d%d", &x, &y);
            if( ma[x][y] != 1 )
            {
                ma[x][y] = 1;
                vis[y]++;
            }
        }
        topo_sort();
    }

    return 0;
}

树中距离最大的两个结点之间的距离称为树的直径。

也是好模板

//#include <bits/stdc++.h>
#include <iostream>
#include <stdio.h>
#include <queue>
#include <string.h>
using namespace std;
const int MAXN = 10000+10;
int dis[MAXN];      // 保存起始节点到当前节点的距离
int vis[MAXN];      // 标记节点已经走过
int ans = 0;
vector< pair<int,int> > v[MAXN];

int BFS( int x )
{
    memset(dis, 0, sizeof(dis));
    memset(vis, 0, sizeof(vis));
    queue<int> q;
    q.push(x);
    vis[x] = 1;
    int poi = 0;
    while( !q.empty() )
    {
        int temp = q.front();
        q.pop();
        if( dis[temp] > ans )   // 如果到当前节点的距离大于已知的最长距离
        {
            ans = dis[temp];
            poi = temp;
        }
        pair<int, int> t;
        for( int i=0; i<v[temp].size(); i++ )
        {
            t = v[temp][i];
            if( vis[t.first] == 0 )
            {
                 vis[t.first] = 1;
                 dis[t.first] = dis[temp] + t.second;   // 保存到下一个节点的距离
                 q.push(t.first);
            }
        }
    }
    return poi;
}
int main()
{
    int a, b, c;    // a到b权值为c的边
    char ch;
    while( scanf("%d%d%d", &a, &b, &c) != EOF )
    {
        v[a].push_back(make_pair(b,c));
        v[b].push_back(make_pair(a,c));
    }
    ans = 0;
    int point = BFS(6); // 从任意一个节点开始搜索
    ans = 0;
    BFS(point);
    printf("%d\n", ans);

    return 0;
}

如果是二维的在图中搜索，改一下就好了

//#include <bits/stdc++.h>
#include <stdio.h>
#include <queue>
#include <iostream>
#include <string.h>
using namespace std;
const int MAXN = 1000+10;

char ma[MAXN][MAXN];    // 存图
int dis[MAXN][MAXN];    // 保存距离
int vis[MAXN][MAXN];    // 标记是否走过
int m, n;
int ans;
int d[4][2] = { 1, 0, -1, 0, 0, 1, 0, -1 }; // 方向数组
inline pair<int,int> BFS(int x, int y)
{
    memset(dis, 0, sizeof(dis));
    memset(vis, 0, sizeof(vis));
    queue< pair<int,int> > q;
    q.push(make_pair(x,y));
    vis[x][y] = 1;
    pair<int,int> point;
    while( !q.empty() )
    {
        pair<int,int> temp;
        temp = q.front();
        q.pop();
        if( dis[temp.first][temp.second] > ans )
        {
            ans = dis[temp.first][temp.second];
            point = temp;
        }
        for( int i=0; i<4; i++ )
        {
            int dx = temp.first + d[i][0];
            int dy = temp.second + d[i][1];
            if( dx >=0 && dx < n && dy >= 0 && dy < m && ma[dx][dy] == '.' && vis[dx][dy] != 1 )
            {
                vis[dx][dy] = 1;
                dis[dx][dy] = dis[temp.first][temp.second] + 1;
                q.push(make_pair(dx,dy));
            }
        }
    }
    return point;
}

int main()
{
    /* 这道题求得是最大的 . 的连通距离 */
    int t;
    scanf("%d", &t);
    while( t-- )
    {
        scanf("%d%d", &m, &n);
        for( int i=0; i<n; i++ )
            scanf("%s", ma[i]);
        pair<int,int> p;
        for( int i=0; i<n; i++ )
        {
            for( int j=0; j<m; j++ )
            {
                if( ma[i][j] == '.' )
                {
                    ans = 0;
                    p = BFS(i, j);
                    goto out;  // 前几次这里就只写了一个break，结果超时，写一个只终止了内层循环
                }
            }
        }
        out:
        ans = 0;
        BFS(p.first, p.second);
        printf("Maximum rope length is %d.\n", ans);
    }

    return 0;
}